题解 | #Flip Game#

题意：给出初始的棋盘，每按一个地方周围上下左右都要翻转，求全部翻转成同样颜色的最小步骤；
可以先把棋盘转化为01棋盘 a数组装黑***r> 例如
bwbw
wwww
bbwb
bwwb
a数组为
0101
0000
1101
1001

#include<cstdio>
#include<cstring>
using namespace std;
const int N=5;
char g[N][N],a[N][N],b[N][N];
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};

void turn (int x,int y)//翻转函数
{
    for(int i=0;i<5;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=4||a<0||b<0||b>=4) continue;
        g[a][b]^=1;//0和1的转换
    }
}

int solve(char c[][5])
{
    int res=100000000;
  for(int op=0;op<16;op++)
  {  int cnt=0;
      memcpy(g,c,sizeof g);
      //处理第一行棋子
      for(int i=0;i<4;i++)
        if(op>>i&1)
      {
          turn(0,i);
          cnt++;
      }
      //处理1~3行棋子
      for(int i=0;i<3;i++)
        for(int j=0;j<4;j++)
      {
          if(g[i][j]=='0')
          {
              turn(i+1,j);
              cnt++;
          }
      }
      //检查最后一行棋子是否成功；
      bool flag=true;
      for(int i=0;i<4;i++)
        if(g[3][i]=='0') flag=false;
        //成功更新答案
      if(flag&&res>cnt) res=cnt;


  }
     return res;
}

int main()
{
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
    {
        char c;
        cin>>c;
        if(c=='b') {a[i][j]='1';b[i][j]='0';}
        else {b[i][j]='1';a[i][j]='0';}
    }
    int res;
    res=solve(a);
    res=min(res,solve(b));
    if(res<100000000)
    cout<<res<<endl;
    else puts("Impossible");
    return 0;
}