显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
//wuli 暴力搜索
using namespace std;
const int Move[5][5]={{0,0},{0,-1},{0,1},{-1,0},{1,0}};
bool A[6][6];
bool flag[6][6];
int f[6][6][888];
int Ans=99999999;
void sou(int,int,int);
//b-> 0,w -> 1
int main()
{
freopen("flip.in","r",stdin);
freopen("flip.out","w",stdout);
char ch;
int tot=0;
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
scanf(" %c",&ch);
if(ch=='w')
{
A[i][j]=1;
tot++;
}
}
}
if(tot==0||tot==16)
{
printf("0");
return 0;
}
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
sou(i,j,1);
}
}
if(Ans==99999999)printf("Impossible");
else printf("%d",Ans);
fclose(stdin);
fclose(stdout);
return 0;
}
void sou(int x,int y,int step)
{
if(f[x][y][step]>556)return;
f[x][y][step]++;
flag[x][y]=1;
for(int i=0;i<5;i++)
{
int xx=x+Move[i][0],yy=y+Move[i][1];
//if(xx<1||xx>4||yy<1||yy>4)continue;
A[xx][yy]=!A[xx][yy];
}
int tot=0;
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
tot+=A[i][j];
}
}
if(tot==0||tot==16)
{
Ans=min(Ans,step);
flag[x][y]=0;
for(int i=0;i<5;i++)
{
int xx=x+Move[i][0],yy=y+Move[i][1];
//if(xx<1||xx>4||yy<1||yy>4)continue;
A[xx][yy]=!A[xx][yy];
}
return;
}
else
{
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
if(!flag[i][j])
{
sou(i,j,step+1);
}
}
}
flag[x][y]=0;
for(int i=0;i<5;i++)
{
int xx=x+Move[i][0],yy=y+Move[i][1];
//if(xx<1||xx>4||yy<1||yy>4)continue;
A[xx][yy]=!A[xx][yy];
}
}
}