输入
2
2
01
10
10
01
2
01
01
11
00
输出
2
-1
解析:此题看到数据范围,直接DFS暴力即可,暴力枚举每行每列是否需要翻转,因为翻转两次是没有意义的。
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
#define endl '\n'int x[5],y[5],n;
int a[5][5],b[5][5],res,c[5][5];
int cal(){int cnt = 0;for (int i = 1; i <= n; ++i) {cnt += x[i] + y[i];}return cnt;
}
void flipx(int xx){for (int i = 1; i <= n; ++i) {c[xx][i] ^= 1;}
}
void flipy(int yy){for (int i = 1; i <= n; ++i) {c[i][yy] ^= 1;}
}
bool check(){for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {c[i][j] = a[i][j];}}for (int i = 1; i <= n; ++i) {if (x[i]) flipx(i);if (y[i]) flipy(i);}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (c[i][j] != b[i][j]) return false;}}return true;
}
void dfs(int step){if (step == n * 2 + 1){if (!check()) return;if (res == -1) res = cal();else res = min(res,cal());return;}if (step <= n){for (int i = 0; i <= 1; ++i) {x[step] = i;dfs(step + 1);}}else{for (int i = 0; i <= 1; ++i) {y[step - n] = i;dfs(step + 1);}}
}
void solve(){res = -1;cin >> n;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> a[i][j];}}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> b[i][j];}}dfs(1);cout << res << endl;
}
signed main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T = 1;cin >> T;while (T--) solve();}