If you naively perform all the operations, replacements occur up to \(\Theta(N^3)\) times. Can we exploit the property of the operation to optimize it?

When \(x\) and \(y\) are between \(i\) and \(N + 1 - i\), inclusive, the color of square \((y, N + 1 - x)\) is replaced with that of square \((x, y)\); here, notice that this replacement is independent of \(i\). Also, \(x\) and \(y\) are between \(i\) and \(N + 1 - i\) if and only if \(y\) and \(N + 1 - x\) are between \(i\) and \(N + 1 - i\).

How does the original square \((x, y)\) correspond to the square after an operation? (Every operation can be regarded as a bijection on \(\lbrace 1,2,\ldots, N \rbrace^2\); we consider the correspondence by this.)

By the discussion above, if \(x\) and \(y\) are between \(i\) and \(N + 1 - i\), the square corresponding to an original square \((x, y)\) transitions as \((x, y) \to (y, N + 1 - x) \to (N + 1 - x, N + 1 - y) \to (N + 1 - y, x) \to (x, y) \to \cdots\).

Thus, if the number of indices \(i\) such that \(x\) and \(y\) are between \(i\) and \(N + 1 - i\), the original square \((x, y)\) corresponds to the square obtained by applying the replacement \((x, y) \mapsto (y, N + 1 - x)\), \(c\) times. Since this loops back after applying four times, we can take the remainder when dividing \(c\) by \(4\), to know corresponding squares before and after the operations by applying the operation at most \(3\) times. (It may help intuitive understanding to regard that the operation is a rotation with respect to the center of the grid.)

The value \(c\) can be explicitly written out as \(\min(x, N + 1 - x, y, N + 1 - y)\). Now that every square has been corresponded to a square in the resulting grid, the answer can be obtained in a total of \(O(N^2)\) time.

Sample code

#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';
	}
}