POJ 1753(用到了状态压缩)

2/22/2017来源:ASP.NET技巧人气:1421

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int step;
int bfs(int start){
	queue<int> Queue;
	int book[65536],last=start;
	memset(book,0,sizeof(book));
	Queue.push(start);
	book[start]=1;
	step=0;
	while(!Queue.empty()){
		int head=Queue.front();
		Queue.pop();
		if(head==0||head==65535){
			return 1;
		}
		for(int i=0;i<16;i++){
			int temp=head^(1<<i);
			if((i+1)%4)
				temp=temp^(1<<(i+1));
			if(i%4)
				temp=temp^(1<<(i-1));
			if(i>3)
				temp=temp^(1<<(i-4));
			if(i<12)
				temp=temp^(1<<(i+4));
			if(!book[temp]){
				book[temp]=1;
				Queue.push(temp);
			}
		}
		if(head==last){
			step++;
			last=Queue.back();
		}
	}
	return 0;
}
int main(){
	char ch;
	int t,start=0;
	for(int i=0;i<16;i++){
		ch=getchar();
		t=(ch=='b'?1:0);
		start=(t<<i)+start;
		if((i+1)%4==0){
			getchar();
		}
	}
	int flag=bfs(start);
	if(flag){
		cout<<step<<endl;
	}
	else{
		cout<<"Impossible\n";
	}
	return 0;
}