题意

题目中的意思是，给出一个由 0 和 1 组成的矩阵块，每次按压之后，按压的那一块，其上下左右四面的块的状态都会改变状态，问哪一种按压方法，可以在按压的次数最少的情况下使得矩阵全部为 0，最后输出矩阵。

思路

这个在操作的时候，每一个块一定要尽可能的少操作，因为操作偶数次会恢复初始状态，并且由题意知道，操作的顺序对解结果没有影响，所以我们可以先给定第一行的状态，再由第一行去逐一判断下一行，直到最后看一看是不是合法就好了。

这里的第一行的操作的枚举，可以使用二进制来进行，快速方便，简记做如下代码：

for(int i = 0;i < (1<<n); ++i){
    memset(jge,0,sizeof(jge));
    for(int j = 0;j < n; ++j){
        jge[0][n-j-1] = i>>j&1;
    }
}

有这几行代码给出的数组的第一行，就是不同的操作状态，也就是每一种我们都去模拟一下，最后看看哪一个最小。

• find 函数用于查询和合法性检验，给出经过当前所有已有的操作后，此块是否变为 0 的检验。
• js 函数用于计算，给出某一个 块 是否按压的记录，并且检查当前的操作是否合法，不合法就输出 IMPOSSIBLE ，否则累加当前状态的操作数，看看是不是当前最优操作。
• filp 函数是主体函数，给出模拟状态，判断最优解是否存在，输出结果。
  大体就这么个思路，下面给出代码。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <functional>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <climits>
typedef long long ll;
using namespace std;
const int maxn = 100;
const int dx[5] = {-1,0,0,0,1};
const int dy[5] = {0,-1,0,1,0};
int org[maxn][maxn], jge[maxn][maxn], ans[maxn][maxn];
//origin / judge / answer
int n, m;

inline int find(int x, int y){
    int res = org[x][y];
    for(int i = 0;i < 5; ++i){
        int nx = x + dx[i],ny = y + dy[i];
        if(nx >= 0 && nx < m && ny >= 0 && ny < n){
            res += jge[nx][ny];
        }
    }
    return (res&1);
}

inline int js(){
    for(int i = 1;i < m; ++i){
        for(int j = 0;j < n; ++j){
            if(find(i-1, j)){
                jge[i][j] = 1;
            }
        }
    }
    for(int i = 0;i < n; ++ i){
        if(find(m-1,i))
            return -1;
    }
    int rs = 0;
    for(int i = 0;i < m; ++i){
        for(int j = 0;j < n; ++j){
            rs += jge[i][j];
        }
    }
    return rs;
}

inline int flip(){
    int res = -1;
    for(int i = 0;i < (1<<n); ++i){
        memset(jge,0,sizeof(jge));
        for(int j = 0;j < n; ++j){
            jge[0][n-j-1] = i>>j&1;
        }
        cout << endl;
        int num = js();
        if(num >= 0 && (res < 0 || res > num)){
            res = num;
            memcpy(ans,jge,sizeof(jge));
        }
    }
    if (res < 0){
        cout << "IMPOSSIBLE" << endl;
    }
    else {
        for(int i = 0;i < m; ++i){
            cout << ans[i][0];
            for(int j = 1;j < n; ++j){
                cout << " " << ans[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}


int main(int argc, char const *argv[])
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin >> m >> n){
        memset(org,0,sizeof(org));
        for(int i = 0;i < m; ++i){
            for(int j = 0;j < n; ++j){
                cin >> org[i][j];
            }
        }
        flip();
    }
    return 0;
}