1.题目描述：点击打开链接
2.解题思路：本题利用暴力搜索解决。不过要采用适当的枚举策略才能防止TLE。由于题目中n的最大值是15，通过观察可以发现，我们可以根据第一行的情况即可推算出下面各行的解，也就是说整个矩阵的解完全取决于第一行的情况。又因为每个元素非0即1，所以可以想到枚举集合。这样，每次枚举第一行的一个状态，然后用check函数去计算改变的个数，无解时输出INF。这样整道题的时间复杂度是O(2^N*N^2)。本题的解法中有一个巧妙之处：每次可以先算一个元素的上，左，右三个元素（如果存在）之和，，然后MOD 2就是它下一个元素应该的值，如果原来是0，而正确的是1，那么相当于把0变成了1；如果原来是0，正确的也是0，那么不变；如果原来是1，正确的是0，那么无解；由此只用判断此时是否无解即可。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 20#define INF 1000000000int A[N][N], B[N][N];int n;int check(int s){memset(B, 0, sizeof(B));for (int c = 0; c < n; c++)if (s&(1<<c))B[0][c] = 1;else if (A[0][c] == 1)return INF;//1不能变成0for (int r = 1; r < n; r++)for (int c = 0; c < n; c++){int sum = 0;//元素B[r-1][c]的上，左，右3个元素之和if (r>1)sum += B[r – 2][c];if (c>0)sum += B[r – 1][c – 1];if (c < n – 1)sum += B[r – 1][c + 1];B[r][c] = sum % 2;//计算出B[r][c]应该的值if (A[r][c] == 1 && !B[r][c])return INF;//如果A[r-1][c]==1但正确的应该是0，那么无解}int cnt = 0;for (int r = 0; r < n;r++)for (int c = 0; c < n;c++)if (A[r][c] != B[r][c])//统计发生改变的0的个数cnt++;return cnt;}int main(){//freopen("t.txt", "r", stdin);int T;cin >> T;for (int rnd = 1; rnd <= T; rnd++){cin >> n;for (int r = 0; r < n;r++)for (int c = 0; c < n; c++)cin >> A[r][c];int ans = INF;for (int s = 0; s < (1 << n); s++)//枚举第一行的所有情况ans = min(ans, check(s));if (ans == INF)ans = -1;printf("Case %d: %d\n", rnd, ans);}return 0;}
你在无垠的海边第一次听到了自己心跳的声音，
