Fliptile

题意：给一个矩阵，矩阵内元素非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;
}