题解 P1764 【翻转游戏 (加强版)】

razx · 2019-11-26 22:52:00 · 题解

枚举＋搜索+位运算。

如果从上往下逐层翻转棋子的话，当前一层必须要修复上一层的不符合目标状态的棋子，换句话说：当第一行的操作方式即操作后的状态已经确定后，下一层的操作方式也就唯一确定了，所以只需枚举出第一行的所有可能状态即可逐行往下翻转操作类推出结果（分两次类推，一次是类推出全部棋子白色向上的目标状态，一次是类推出全部棋子黑色向上的目标状态）。 关键代码注释已有，就不细说了。

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

int Map[20][20];
int n,ans =(1<<31)-1;

void Flip(int x,int y)
{
  Map[x-1][y] ^= 1;
  Map[x][y-1] ^= 1;
  Map[x][y] ^= 1;
  Map[x][y+1] ^= 1;
  Map[x+1][y] ^= 1;
}

void Dfs(int row,int step,int value)
{
  if(row == n+1)
  {
    for(int i = 1; i <= n; i++)
      if(Map[n][i]==value)          //若不符合，退出
        return;
    ans=step<ans?step:ans;          //符合则更新答案
    return;
  }
  int v = 0;
  for(int i = 1; i <= n; i++)
    if(Map[row-1][i]==value)        //上一层的某棋子不是目标状态，则翻转
    {
      step++;
      Flip(row,i);                  //翻转当前层以改变上一层的棋子
      v |= 1<<(i-1);                //记录翻转的位置
    }
  Dfs(row+1,step,value);
  for(int i = 1; i <= n; i++)       //还原
    if((v>>(i-1))&1)
      Flip(row,i);
}

int main()
{
  cin >> n;
  char ch;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    {
      cin >> ch;
      Map[i][j] =(ch=='b');
    }
  for(int k = 0; k <(1<<n); k++)
  {
    for(int i = 1; i <= n; i++)     //枚举出第0行(不存在的行)的所有状态
      Map[0][i]=(k>>(i-1))&1?1:0;
    Dfs(1,0,0);                     //从第1行开始，搜索能不能找到全为1的状态
    Dfs(1,0,1);                     //从第1行开始，搜索能不能找到全为0的状态
  }
  if(ans!=(1<<31)-1)
    cout<<ans<<endl;
  else
    cout<<"Impossible"<<endl;
  return 0;
}