すべての操作を愚直に行うと、置き換えの回数は合計で \(\Theta(N^3)\) 回となってしまいます。そこで、操作の性質に注目して置き換えを高速に行うことを考えましょう。

\(x, y\) が \(i\) 以上 \(N + 1 - i\) 以下であるとき、マス \((y, N + 1 - x)\) の色はマス \((x, y)\) の色で置き換えられますが、この置き換えは \(i\) に依存しないことに注目します。また、\(x, y\) が \(i\) 以上 \(N + 1 - i\) 以下であることと \(y, N + 1 - x\) が \(i\) 以上 \(N + 1 - i\) 以下であることは同値です。

元のマス \((x, y)\) は操作後ではどのマスに対応しているか考えましょう（すべての操作は \(\lbrace 1,2,\ldots, N \rbrace^2\) 上の全単射と捉えることができ、これによる対応を考えています）。

上の議論から、\(x, y\) が \(i\) 以上 \(N + 1 - i\) 以下であるとき操作によって元のマス \((x, y)\) が対応するマスは \((x, y) \to (y, N + 1 - x) \to (N + 1 - x, N + 1 - y) \to (N + 1 - y, x) \to (x, y) \to \cdots\) と変化していきます。

したがって、\(x, y\) が \(i\) 以上 \(N + 1 - i\) 以下であるような \(i\) の個数を \(c\) とおくと、\((x, y) \mapsto (y, N + 1 - x)\) というような操作を \(c\) 回行った後のマスが元のマス \((x, y)\) と対応するマスであり、この操作は \(4\) 回行うことで元に戻るので \(c\) を \(4\) で割った余りを取り、高々 \(3\) 回の操作を行うことで操作前と操作後のマスの対応がわかります（操作はグリッドの中央を中心とした回転だと捉えられるので、このように考えると直感的な理解が簡単になるでしょう）。

\(c\) の値は具体的に \(\min(x, N + 1 - x, y, N + 1 - y)\) と書け、すべてのマスに対し定数回の計算を行うことで操作後のマスとの対応が得られたので、全体として \(O(N^2)\) 時間で計算できます。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
	int n;
	cin >> n;
	vector<vector<char>> a(n, vector<char>(n));
	rep(i, n) rep(j, n) cin >> a[i][j];
	vector<vector<char>> ans(n, vector<char>(n));
	rep(i, n) rep(j, n) {
		int d = min({ i + 1, j + 1, n - i, n - j });
		int ni = i, nj = j;
		rep(_, d % 4) {
			int ti = nj, tj = n - 1 - ni;
			ni = ti, nj = tj;
		}
		ans[ni][nj] = a[i][j];
	}
	rep(i, n) {
		rep(j, n) {
			cout << ans[i][j];
		}
		cout << '\n';
	}
}