传送门 枚举第一行的状态，然后向下进行递推，假设我们枚举的每个答案都是正确的，那就不可能从第一行进行翻转，此时如果第一行还有0那么就必须是第二行对应位置进行翻转，然后就依次向下进行递推。 还有一种写法是从全1的情况逆向翻转找到所有合法情况进行hash，本题数据小也能过。
#include<bits/stdc++.h> using namespace std; char mp[10][10], g[10][10]; int n = 5; int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; void turn(int x, int y) ///翻转x, y和其四周 { g[x][y] ^= 1; for(int i = 0; i < 4; ++i) { int tx = x+dx[i], ty = y+dy[i]; g[tx][ty] ^= 1; } } bool check() ///是否合法 { for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if(g[i][j] == '0') return false; return true; } void solve() { for(int i = 0; i < n; ++i) scanf(" %s", mp[i]); int ans = 10; for(int i = 0; i < (1<<n); ++i) { int c = 0; memcpy(g, mp, sizeof(mp)); for(int j = 0;j < n; ++j) { if(i>>j&1) { turn(0, j); c++; } } for(int j = 1; j < n; ++j) { for(int k = 0; k < n; ++k) { if(g[j-1][k]=='0') turn(j, k), c++; } } if(check()) ans = min(ans, c); } if(ans > 6) ans = -1; printf("%d\n", ans); } int main() { int _; scanf("%d", &_); while(_--) solve(); return 0; }