AOJ 2731 Shifting a Matrix
解説
シフト操作 F について,F[i][j] := i 行目 j 列目の要素がどこに移るか と表現すれば,あとはこれらを結合するだけです.操作 F, G に対し,これらをこの順に結合した操作 H は H[i][j] = F[G[i][j].first][G[i][j].second] と計算できます.
操作回数が大きいので,行列のシフト操作は繰り返し二乗法っぽく計算します.
変に解説するよりコードを読んでもらったほうが早いと思います.
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int N; vector<vector<pii>> make_initial() { vector<vector<pii>> res(N, vector<pii>(N)); for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { res[i][j] = make_pair(i, j); } } return res; } vector<vector<pii>> eval(vector<vector<pii>> const& A, vector<vector<pii>> const& x) { auto res = A; for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { res[i][j] = A[x[i][j].first][x[i][j].second]; } } return res; } vector<vector<pii>> sequence(string const& s, int& p); vector<vector<pii>> repetition(string const& s, int& p); vector<vector<pii>> operation(string const& s, int& p); int number(string const& s, int& p); vector<vector<pii>> sequence(string const& s, int& p) { auto res = make_initial(); while(p < s.size() && (s[p] == '(' || isalpha(s[p]))) { vector<vector<pii>> f; if(s[p] == '(') { f = repetition(s, p); } else if(isalpha(s[p])) { f = operation(s, p); } else { cout << "error pos: " << p << endl; assert(false); // error } res = eval(res, f); } return res; } vector<vector<pii>> repetition(string const& s, int& p) { auto x = sequence(s, ++p); ++p; assert(isdigit(s[p])); int n = number(s, p); auto res = make_initial(); while(n > 0) { if(n & 1) { res = eval(res, x); } x = eval(x, x); n >>= 1; } return res; } vector<vector<pii>> operation(string const& s, int& p) { auto res = make_initial(); char op = s[p++]; int i = number(s, p) - 1; if(op == 'L') { for(int j = 0; j < N; ++j) { res[i][j].second = (j + 1) % N; } } else if(op == 'R') { for(int j = 0; j < N; ++j) { res[i][j].second = (j - 1 + N) % N; } } else if(op == 'U') { for(int j = 0; j < N; ++j) { res[j][i].first = (j + 1) % N; } } else if(op == 'D') { for(int j = 0; j < N; ++j) { res[j][i].first = (j - 1 + N) % N; } } else { assert(false); } return res; } int number(string const& s, int& p) { int res = 0; while(isdigit(s[p])) { res *= 10; res += (s[p++] - '0'); } return res; } int main() { int L; string S; cin >> N >> L >> S; int p = 0; auto ans = sequence(S, p); for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { cout << (ans[i][j].first * N + ans[i][j].second + 1) << " \n"[j + 1 == N]; } } }