在一个nxm的图中，一个牛踩格子，踩一个格子上下左右和自己所在的格子都会翻转，1表示黑色，0表示白色。想要用最少的步数踩成全白，输出一个nxm的图，1表示踩，0表示不踩。
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>using namespace std;int n, m, flag, sum;
bool a[20][20];
bool b[20][20];
int ans[20][20];
int Z_ans[20][20];
int c[20];bool check() //在第一排反转的情况下，是否符合
{flag = 1;memset(ans, 0, sizeof(ans));for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {b[i][j] = a[i][j];}}for(int i = 0; i < m; i++){if(c[i]) {b[0][i] = !b[0][i];ans[0][i] = 1;if(1 < n) {b[1][i] = !b[1][i];}if(i + 1 < m) {b[0][i + 1] = !b[0][i + 1];}if(i - 1 >= 0) {b[0][i - 1] = !b[0][i - 1];}}}for(int i = 0; i < n - 1; i++) {for(int j = 0; j < m; j++) {if(b[i][j]) {b[i + 1][j] = !b[i + 1][j];ans[i + 1][j] = 1;if(i + 2 < n) {b[i + 2][j] = !b[i + 2][j];}if(j + 1 < m) {b[i + 1][j + 1] = !b[i + 1][j + 1];}if(j - 1 >= 0) {b[i + 1][j - 1] = !b[i + 1][j - 1];}}}}for(int i = 0; i < m; i++) {if(b[n - 1][i] == 1) {flag = 0;break;}}int t = 0;if(flag) {for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(ans[i][j] == 1) {t++;}}}if(t < sum) {sum = t;for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {Z_ans[i][j] = ans[i][j];}}}}
}void dfs(int t) //列举第一排翻转的所有情况
{if(t > m)return;if(t == m) {check();}for(int i = 0; i <= 1; i++) {c[t] = i;dfs(t + 1);}
}int main()
{while(cin >> n >> m) {flag = 0;memset(ans, 0, sizeof(ans));memset(c, 0, sizeof(c));for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {cin >> a[i][j];}}sum = 1000000;dfs(0);if(sum != 1000000) {for(int i = 0; i < n; i++) {cout << Z_ans[i][0];for(int j = 1; j < m; j++) {cout << ' ' << Z_ans[i][j];}cout << endl;}}elsecout << "IMPOSSIBLE" << endl;}return 0;
}