首先去要知道的是,每个点至多翻转一次,如果翻转第二次的话,将会无限循环,所以可以枚举每一步中翻转任意一个点的结果情况。
位运算想要达到翻转某一位上数字的目的,需要用1来异或该位,也就是1左移该位的位数-1,然后去异或 1^1=0 0^1=1,然后也不用担心一左移以后后面的0会修改其它的位,因为 0^0=0 1^0=1,也就是 x^0=x 位运算优势就是更快,占空间更小
#include<iostream>
#include<queue>
using namespace std;
const int M=7e4;
int vis[M];
int minn=0;
int maxn=65535;
struct node{
int val;
node(int a){val=a; }
node(){}
};
queue<node> q;
int change(int x,int y,int val){
int k=1<<(x*4+y);
val^=k;
if(y>0){ //左
int k=1<<(x*4+(y-1));
val^=k;
}
if(y<3){ //右
int k=1<<(x*4+(y+1));
val^=k;
}
if(x>0){ //上
int k=1<<((x-1)*4+y);
val^=k;
}
if(x<3){
int k=1<<((x+1)*4+y);
val^=k;
}
return val;
}
int step;
int bfs(){
while(!q.empty()){
int t=q.size();
for(int k=0;k<t;k++){
node tmp=q.front();
q.pop();
if(tmp.val==minn||tmp.val==maxn||step>16){
return step;
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
int next=change(i,j,tmp.val);
if(vis[next])
continue;
vis[next]=1;
q.push(node(next));
}
}
}
++step;
}
}
int main(){
char ch[10];
int state=0;
for(int i=0;i<4;i++){
cin>>ch;
for(int j=0;j<4;j++){
int k=i*4+j;
if(ch[j]=='b')
state+=1<<k;
}
}
vis[state]=1;
q.push(node(state));
int ans=bfs();
if(ans>16) cout<<"Impossible"<<endl;
else cout<<ans<<endl;
// cout<<state<<endl;
return 0;
}