ddd

柯昊阳  •  1年前


include <bits/stdc++.h>

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;

}


评论: