题意:给一个矩阵,矩阵内元素非0即1且各元素可以翻转,0可以翻转为1,1可以翻转为0,翻转某一个元素时,它的上下左右个元素也会翻转
(注:受影响翻转的不会继续影响其它的),先问是否可以成功将元素全部置0,若可以,输出翻转次数最小的,若有多个答案,按字典序输出
思路:首先因为翻转一个元素会造成许多连锁反映,我们只枚举第一行所有可能的操作(比如第一个元素翻转,第二个不翻转,第一个翻转,第二个不翻转等等等等,类似于一个全排列,总共2^m种)
然后第一行就不动了,接着遍历第一行所有列,找到为1的元素,这个时候,这个1就只能靠它下面的元素翻转来使它成为0(这样才不会改变第一行其它元素的排列状态)
然后后面每行以此类推,然后检查最后一行,若最后一行还有为1的元素则说明这种排列不能让它全为0,然后继续循环下一种第一行的排列方式
#include<iostream> #include<string.h> using namespace std; const int INF = 1000000; int m, n; int g[20][20]; int fliped[20][20]; int res[20][20]; int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1}; bool is_successful; void flip(int x, int y){ fliped[x][y] = 1; for(int i=0; i<5; i++){ int nx = dx[i] + x; int ny = dy[i] + y; if(nx >= 0 && nx < m && ny >= 0 && ny < n) g[nx][ny] = 0 + (1 - g[nx][ny]); } } void work(){ int MIN = INF; bool flag; for(int k=0; k< 1<<n; k++){ int steps = 0; int backup[20][20]; memcpy(backup, g, sizeof g); memset(fliped, 0, sizeof(fliped)); for(int i=0; i<n; i++) if(k >> i & 1){ steps++; flip(0, i); } for(int i=0; i<m-1; i++){ for(int j=0; j<n; j++){ if(g[i][j] == 1){ steps++; flip(i+1, j); } } } flag = true; for(int i=0; i<n; i++) if(g[m-1][i] == 1){ flag = false; break; } if(steps < MIN && flag){ MIN = steps; memcpy(res, fliped, sizeof(fliped)); } memcpy(g, backup, sizeof(backup)); } if(MIN == INF) is_successful = false; } int main(){ ios::sync_with_stdio(false); while(cin >> m >> n){ for(int i=0; i<m; i++) for(int j=0; j<n; j++) cin >> g[i][j]; memset(res, 0, sizeof(res)); is_successful = true; work(); if(is_successful){ for(int i=0; i<m; i++){ for(int j=0; j<n; j++) cout << res[i][j] << " "; cout << endl; } }else cout << "IMPOSSIBLE" << endl; } return 0; }