1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 using namespace std; 8 9 const int INF = 0xfffffff;10 int g[17][17];11 int f[17][17] = {};12 int ans[17][17] = {};13 int mmin = INF;14 15 bool judge(int n,int m)//判断最后一行是否全为016 {17 for(int i=1;i<=m;i++)18 {19 int t = f[n][i]+f[n][i-1]+f[n][i+1]+f[n-1][i];20 if( (g[n][i]+t)&1 )21 return false;22 }23 return true;24 }25 26 void dfs(int n,int m,int k,int num)27 {28 if(num > mmin)//剪枝29 return;30 if(k > n)31 {32 if(judge(n, m) && mmin>num)//判断是否符合条件33 {34 memcpy(ans, f, sizeof(f));35 mmin = num;36 }37 return;38 }39 int t = 0;40 for(int i=1;i<=m;i++)41 {42 if((g[k-1][i]+f[k-2][i]+f[k-1][i-1]+f[k-1][i+1]+f[k-1][i])&1)//上一行是否为1，即是否需要翻转43 {44 f[k][i] = 1;45 t++;46 }47 else48 f[k][i] = 0;49 }50 dfs(n, m, k+1, num+t);51 }52 53 //n,m行列数 k当前列 num第一行翻转的次数54 void todfs(int n, int m, int k, int num)55 {56 if(k > m)57 {58 dfs(n, m, 2, num); //对第一行每种情况进行搜索59 return;60 }61 f[1][k] = 0; //不翻转62 todfs(n, m, k+1, num);63 f[1][k] = 1; //翻转，num＋164 todfs(n, m, k+1, num+1);65 }66 67 int main()68 {69 int n,m;70 cin >> n >> m;71 for(int i=1;i<=n;i++)72 for(int j=1;j<=m;j++)73 cin>>g[i][j];74 todfs(n, m, 1, 0); //递归遍历第一行所有情况75 if(mmin == INF)76 cout<<"IMPOSSIBLE"<