提交时间:2024-01-23 10:14:26
运行 ID: 123924
#include <bits/stdc++.h> using namespace std; queue<int> 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; }