柯昊阳 • 1年前
using namespace std; queue que; bool flag[65536]; int step[65536]; int Flip(int state,int pos){
state^=(1<<pos);
state^=((pos-4)>=0)<<(pos-4);
state^=((pos+4)<=15)<<(pos+4);
state^=(pos%4!=0)<<(pos-1);
state^=(pos%4!=3)<<(pos+1);
return state;
} int BFS(){
while(que.empty()!=1){
int state = que.front();
que.pop();
for(int i = 0;i<16;i++){
int temp = Flip(state,i);
if(temp==0||temp==65535){
flag[temp] = 1;
step[temp] = step[state]+1;
return true;
}
else if(!flag[temp]){
que.push(temp);
flag[temp] = 1;
step[temp] = step[state]+1;
}
}
}
return false;
} int main(){
int state = 0;
char s[5];
for(int i = 0;i<4;i++){
cin>>s;
for(int j = 0;j<4;j++){
state|=((s[j]=='b')<<(i*4+j));
}
}
if(state==0||state==65535){
cout<<"0"<<endl;
}
else{
que.push(state);
flag[state] = 1;
if(BFS()){
printf("%d\n",flag[0]?step[0]:step[65535]);
}
else cout<<"Impossible"<<endl;
}
return 0;
}
评论: