跳转至

黑白翻转棋

keywords: 枚举

题意

题目链接，黑白翻转棋 题意，一个棋盘，每按一个位置，上下左右自己，5个位置的颜色会翻转。请问最少按几次，可以将棋盘变成全部白色。这是一道题目的改编，原题是《费解的开关》，在奥数中也常见。与原题不同的是，降低了数据读入的难度，但是增大了数据强度，很难AC掉

思路1，30pts

逐行逐列，每一位可以按，或者不按。时间复杂度 �(2�∗�) 。

具体递归枚举子集。或者写dfs，选或者不选。

思路2，85pts

在费解的开关里，优化是先枚举第一行的所有翻转方案，因为第一行定下来后，剩下的就是一行一行捋着按就可以了。没有第二种选择。时间复杂度 �(2�∗�∗�) 。

因n, m <= 20，2^20 * 20 * 20 = 1024 * 1024 * 400 = 4e8，这个应该是上下浮动看人品。果然，本题的数据，最后三个点，n和m给的都很大。所以，考察的不仅仅是你会二进制表示方案，还要会优化起来。

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int ret = 0x3f3f3f3f;
int g[N][N], bak[N][N], n, m;

int dx[] = {0, 1, 0, -1, 0}, dy[] = {1, 0, -1, 0, 0};

void change(int x, int y){
    for (int i = 0; i < 5; i++){
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] == 1) g[a][b] = 0;
        else g[a][b] = 1;
    }
}

bool check(){
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j]) return false;

    return true;
}

void backup(int a[][N], int b[][N]){
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            a[i][j] = b[i][j];
}


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

    backup(bak, g);
    for (int mask = 0; mask < (1 << m); mask++){
        backup(g, bak);

        int cnt = 0;
        for (int j = 0; j < m; j++)
            if ((mask >> j) & 1){
                change(0, j);
                cnt++;
            }

        for (int i = 0; i < n - 1; i++){
            for (int j = 0; j < m; j++)
                if (g[i][j]){
                    change(i + 1, j);
                    cnt++;
                }
        }

        if (check()) ret = min(ret, cnt);
    }

    if (ret == 0x3f3f3f3f) cout << "Impossible" << '\n';
    else cout << ret << '\n';

    return 0;
}

思路3，100pts

思路2会超时，很定就是那个 �(∗�∗�) 惹的祸，在代码中，是老老实实 ∗�∗� ，然后按一个格子的时候，是模拟5个点for一遍。在这个环节上，参考了[枚举第一行+位运算]，代老师的这个思路，但我进行了改编。

代码整体框架和思路2一致，区别是用一个二维数组press[i][j]来维护每一个格子的翻转情况。通过格子上原有数字，异或上相关的所有格子的翻转方案(能影响到本格子的)，得到本格子翻转之后的结果。最后，还是看最后一行是否都是0，来判断方案的合法性。

// 下标必须从1开始，否则很多细节越界

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int n, m, ret = 0x3f3f3f3f;
int g[N][N];     // g[i]表示第i行的棋盘，每一行用二进制数表示，用[m位-1位]作为有效位，第0位不用
int press[N][N]; // press[i]表示第i行的翻转方案，二进制数表示，0/1表示是否按了

int check(){
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cnt += press[i][j];

    return cnt;
}

void print(){
    for (int i = 1; i <= m; i++) cout << press[1][i];
    puts("");
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> g[i][j];

    for (int mask = 0; mask < (1 << m); mask++){
        for (int j = 1; j <= m; j++) press[1][j] = mask >> (j-1) & 1;
        for (int i = 1; i <= n - 1; i++)
            for (int j = 1; j <= m; j++){
                press[i + 1][j] = g[i][j] ^ press[i][j] ^ press[i][j - 1] ^ press[i][j + 1];
                if (i > 1) press[i + 1][j] ^= press[i - 1][j];
            }

        bool flag = false;
        for (int j = 1; j <= m; j++){
            int t = g[n][j] ^ press[n][j] ^ press[n][j - 1] ^ press[n][j + 1];
            if (n > 1) t ^= press[n - 1][j];

            if (t){
                flag = true;
                break;
            }
        }

        if (flag) continue;
        ret = min(ret, check());
    }

    if (ret == 0x3f3f3f3f) cout << "Impossible" << '\n';
    else cout << ret << '\n';

    return 0;
}

思路4，100pts

参考[枚举第一行+位运算]，我觉得这个掩码的方法很好，我之前没用过，翻写一遍。还有把每一行的翻转直接维护到一个二进制数当中，从而省去了枚举行的过程，去掉了 �(∗�) ，这提高了很多速度

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int n, m, ret = 0x3f3f3f3f;
int g[N];     // g[i]表示第i行的棋盘，每一行用二进制数表示，用[m位-1位]作为有效位，第0位不用
int press[N]; // press[i]表示第i行的翻转方案，二进制数表示，0/1表示是否按了

int check(){
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        while (press[i]){
            press[i] = press[i] & (press[i] - 1);
            cnt++;
        }

    return cnt;
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        int x;
        for (int j = 1; j <= m; j++){
            cin >> x;
            g[i] <<= 1;
            g[i] |= x;
        }
        g[i] <<= 1;  // 二进制的[m...1位]用来表示状态
    }

    int len = ((1 << m) - 1) << 1; // 11111111111110, m个1，用来控制m个1的
    for (int mask = 0; mask < (1 << m); mask++){
        press[1] = mask << 1; // 第一行的翻转方案
        for (int i = 2; i <= n; i++)
            press[i] = len & (press[i - 2] ^ press[i - 1] ^ (press[i - 1] >> 1) ^ (press[i - 1] << 1) ^ g[i - 1]);

        // 看最后一行是否全是0
        // 最后一行非0，就continue
        int t = len & (press[n - 1] ^ press[n] ^ (press[n] >> 1) ^ (press[n] << 1) ^ g[n]);
        if (t) continue;  

        ret = min(ret, check());
    }

    if (ret == 0x3f3f3f3f) cout << "Impossible" << '\n';
    else cout << ret << '\n';

    return 0;
}

总结

  1. 测试数据中应该没有n=1, m=1的数据，这个数据一出，应该可以hack掉现有的很多代码
  2. 这道题目也学到了很多，所以写一篇文章记录一下
  3. 看了代老师的代码，我本想用 bitset 操作一翻，结果以失败告终，不如使用二进制数可行