Author: lllyouo
Date: 20250812
tag: 简单搜索
link: https://www.luogu.com.cn/problem/P1985

问题描述

link

分析

略

参考代码

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

const int LIMIT = 20;
int m, n;
int g[LIMIT][LIMIT], bg[LIMIT][LIMIT], ans[LIMIT][LIMIT], res[LIMIT][LIMIT];
int min_cnt = 1e9;

void turn(int r, int c) {
    res[r][c]++;
    g[r][c] ^= 1;
    if (r > 0) g[r - 1][c] ^= 1;
    if (r < m - 1) g[r + 1][c] ^= 1;
    if (c > 0) g[r][c - 1] ^= 1;
    if (c < n - 1) g[r][c + 1] ^= 1;
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> bg[i][j];
        }
    }

    // 枚举第一行状态
    for (int op = 0; op < (1 << n); op++) {
        memcpy(g, bg, sizeof g);
        memset(res, 0, sizeof res);
        int cnt = 0;
        
        // 第一行翻转
        for (int j = 0; j < n; j++) {
            if (op >> j & 1) {
                turn(0, j);
                cnt++;
            }
        }

        // 从第二行开始
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i - 1][j] == 1) {
                    turn(i, j);
                    cnt++;
                }
            }
        }
        
        
        // 检查最后一行
        for (int j = 0; j < n; j++) {
            if (g[m - 1][j] == 1) {
                cnt = 1e9;
                break;
            }
        }

        if (cnt < min_cnt) {
            min_cnt = cnt;
            memcpy(ans, res, sizeof ans);
        } 
        else if (cnt == min_cnt && cnt != 1e9) {
            // 字典序比较
            bool updated = false;
            for (int i = 0; i < m && !updated; i++) {
                for (int j = 0; j < n; j++) {
                    if (res[i][j] != ans[i][j]) {
                        if (res[i][j] < ans[i][j]) {
                            memcpy(ans, res, sizeof ans);
                        }
                        updated = true;
                        break;
                    }
                }
            }
        }
    }

    if (min_cnt != 1e9) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cout << ans[i][j] << (j == n - 1 ? '\n' : ' ');
            }
        }
    } 
    else {
        cout << "IMPOSSIBLE" << endl;
    }
    
    return 0;
}