回転操作を行わない場合、\(S\) と \(T\) で一致していないマスの個数が答えです。

マスの色を塗り替える操作と、グリッド全体を回転する操作は、順序を入れ替えても構いません。よってグリッド全体を回転する操作は最初に行うとしてよいです。 回転する操作を行う回数が \(0,1,2,3\) 回のいずれであるかを \(4\) 通り全て試すことでこの問題を解くことができます。

実装例(Python)

N = int(input())
S = [input() for _ in range(N)]
T = [input() for _ in range(N)]

def right_rot90(S):
  return list(zip(*S[::-1]))

def count_diff(S,T):
  return sum([1 for si,ti in zip(S,T) for sij,tij in zip(si,ti) if sij!=tij])

ans = 10**9
for rot_count in range(4):
  ans = min(ans, count_diff(S,T)+rot_count)
  S = right_rot90(S)

print(ans)

実装例(C++)

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

int count_diff(vector<string>S, vector<string>T){
	int N = S.size();
	int ans = 0;
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(S[i][j]!=T[i][j])ans++;
	return ans;
}

vector<string> right_rot90(vector<string>S){
	int N = S.size();
	vector<string>ret(N, string(N,'.'));
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)ret[i][j]=S[N-1-j][i];
	return ret;
}

int main(){
	int n;
	cin >> n;
	vector<string> s(n), t(n);
	for(auto &x:s)cin >> x;
	for(auto &x:t)cin >> x;
	
	int ans = 1e9;
	for(int rot_count=0;rot_count<4;rot_count++){
		ans = min(ans, count_diff(s,t)+rot_count);
		s = right_rot90(s);
	}
	cout << ans << endl;
}