#include<iostream>
#include<string>

using namespace std;

// 16个棋子翻棋，使他全白或全黑，翻一个则上下左右全翻 

const int mx = 1<<16;
int f[mx] = {0};
int pre[mx] = {0};
int qu[mx],e = -1,s = 0;
string str[5];
int b[5] = {0,1,-1,4,-4};

void pri(int t){
	int ff = 15;
	for(int i = 1;i<=4;++i){
		for(int j = 1;j<=4;++j){
			cout << ((t&1<<ff)?1:0) << " ";
			--ff;
		}
		cout <<endl;
	}
	cout <<endl;
}

int main(){
	for(int i = 1;i<=4;++i){
		cin >> str[i];
	}
	int st = 0;
	for(int i = 1;i<=4;++i){
		for(int j = 0;j<4;++j){
			st<<=1;
			if(str[i][j]=='b')++st; 
		}
	}
	qu[++e] = st;
	f[st] = 1;
	int cur,nx,np;
	while(s<=e){
		if(f[0]) break;
		cur = qu[s++];
		for(int i = 15;i>=0;--i){
			nx = cur;
			for(int j = 0;j<5;++j){
				if(i%4==3 &&j==1) continue;
				if(i%4==0 && j==2) continue;
				np = i+b[j];
				if(np<0 || np>15) continue;
				nx^=(1<<np); 
			}
			if(!f[nx]){
				f[nx] = f[cur]+1;
				pre[nx] = cur;
				qu[++e] = nx;
				if(nx==0) break;
			}
		}
	}
	if(f[0] || f[(1<<16)-1]){
		cout << min(f[0],(f[(1<<16)-1]>0?f[(1<<16)-1]:0x3f3f3f3f))-1;
	}else
	    cout << "Impossible";
   
} 

• Re:BFS+二进制 (1286) Xian_ll 2023-04-20 20:55:22