翻转（DAY 97)

1：题目

给定一个 M×N 的 01 矩阵。

你需要选择其中一些元素，并对选择的元素进行翻转操作。

翻转操作是指将所选元素以及与其上下左右相邻的元素（如果有）进行翻转（0 变 1，1 变 0）。

我们希望最终矩阵变为一个全 0 矩阵，并且选择进行翻转操作的元素数量尽可能少。

输出最佳翻转方案。

输入格式
第一行包含整数 M,N。

接下来 M 行，每行包含 N 个整数，每个整数为 0 或 1。

输出格式
共 M 行，每行包含 N 个整数，其中第 i 行第 j 列的整数，表示第 i 行第 j 列元素的翻转次数。

如果翻转操作次数最少的操作方案不唯一，则输出字典序最小的方案。

如果不存在合理方案，则输出 IMPOSSIBLE。

数据范围
1≤M,N≤15
输入样例：
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
输出样例：
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

2：代码实现

#include <bits/stdc++.h>
using namespace std;

#define debug(x...) cerr << (#x) <<" -> ", err(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

#define fi first
#define se second
#define endl '\n'
// #define int long long

void err() {
    
    cerr << '\n';
}
template<class T, class... Ts>
void err(const T &A, const Ts &... other) {
    
    cerr << (A) << ' ';
    err(other...);
}
using PII = pair<int, int>;
using ll = long long;

const int N = 2e6 + 10, INF = 0x3f3f3f3f;
const int mod = 998244353;
int dx[5] = {
    -1, 0, 1, 0, 0}, dy[5] = {
    0, 1, 0, -1, 0};

void solve() {
    
    int n, m, res = INF;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m)), b(n, vector<int>(m));
    vector<vector<int>> ans(n, vector<int>(m, 0));
    for (auto &x : g) 
        for (auto &y : x) 
            cin >> y;

    auto change = [&](int x, int y) {
    
        for (int i = 0; i < 5; i ++) {
    
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || (nx >= n) || ny < 0 || (ny >= m)) continue;
            b[nx][ny] ^= 1;
        }
    };

    for (int i = 0; i < (1 << m); ++ i) {
     // 枚举第一行的所有方案
        b = g;
        int cnt = 0;
        vector<vector<int>> o(n, vector<int>(m, 0));
        for (int j = 0; j < m; ++ j) 
            if (i >> j & 1) 
                change(0, j), o[0][j] = 1, cnt ++;

        for (int j = 0; j < n - 1; ++ j) 
            for (int k = 0; k < m; ++ k) 
                if (b[j][k]) 
                    change(j + 1, k), o[j + 1][k] = 1, cnt ++;

        bool flag = true;
        for (int j = 0; j < m; ++ j) 
            if (b[n - 1][j]) flag = false;

        if (flag and cnt < res) res = cnt, ans = o;
    }

    if (res == INF) {
    
        cout << "IMPOSSIBLE" << endl;
        return;
    }
    for (auto x : ans) {
    
        for (auto y : x) {
    
            cout << y << ' ';
        }
        cout << endl;
    }
}

signed main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ___ = !(0 ^ 0);
    // cin >> ___;
    for (; ___ -- ;) solve();
    return 0;
}