题解 | #Flip Game#

• 题目考点：位运算+01串枚举
• 题目大意：n*m由'w'和'b'石子组成的矩阵，每次选择一个石子按一下，按下之后，该石子以及上下左右的5个石子都会翻转（'w'变成'b','b'变成'w'），问讲矩阵全变成'w'或全变成'b'最少需要按几次，若无解输出Impossible
• 题目分析：经分析得知，若第一行元素确定，则可通过按第二行把第一行全变成指定元素，例如：

  bwbw
  wbwb
  wwww
  wwww

  如上例，如果想要把第一列的第一个b变成w同时不影响第一列，则可以且必须按第二列第一个w，即b后面的那个石子，所以，如果第一列的状态确定，那么第二列的状态也确定了，由此推之，只要确定第一列，后面的石子是否需要按也都确定了。因此我们只需要对第一列的石子进行是否需要按的枚举即可，最后检查每次枚举是否可行，维护最小值答案得解。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 10, INF = 0x3f3f3f3f;
char a[N][N], b[N][N];
int cnt = 0, ans = INF;

void turn(int x, int y)
{
    b[x][y] = b[x][y]=='b'?'w':'b';
    b[x-1][y] = b[x-1][y]=='b'?'w':'b';
    b[x][y-1] = b[x][y-1]=='b'?'w':'b';
    b[x+1][y] = b[x+1][y]=='b'?'w':'b';
    b[x][y+1] = b[x][y+1]=='b'?'w':'b';
    cnt++;
}

void solve(char t)
{
    for(int i = 0; i < (1 << 4); i++) // 枚举0000-1111
    {
        cnt = 0;
        // 先枚举第一列按不按
        memcpy(b, a, sizeof a);
        for(int j = 1; j <= 4; j++)
        {
            if(i & (1<<(j-1))) turn(j, 1);
        }

        // 依次判断2-3列的棋子是否需要按
        for(int k = 2; k <= 4; k++)
        for(int j = 1; j <= 4; j++)
            if(b[j][k-1] != t) turn(j, k);

        // 判断最后一列是否摆放完毕
        for(int j = 1; j <= 4; j++)
            if(b[j][4] != t) cnt = INF;

        // 维护最小值
        ans = min(ans, cnt);
    }
}

int main()
{
    for(int i = 1; i <= 4; i++)
        scanf("%s", a[i]+1);

    // 把所有棋子翻转成两个状态各一次
    solve('w');
    solve('b');

    if(ans != INF)printf("%d", ans);
    else puts("Impossible");
    return 0;
}