poj 1753 Flip Game

http://162.105.81.212/JudgeOnline/problem?id=1753

bfs+状态压缩

16个格子转换成int类型,(b->1, w->0)

则样例

bwbw
wwww
bbwb
bwwb

对应的二进制为:0(16个),1010,0000,1101,1001

而每一次翻转, 可视为将对应位与1进行异或运算,

如翻转第1个格子[坐标(0,0)], 则可看做与0(16个),1100，1000,0000,0000进行异或运算

这样就可以先写出这16个数来:

int dir[]={0xc800,0xe400,0x7200,0x3100,
   		   0x8c80,0x4e40,0x2720,0x1310,
		   0x08c8,0x04e4,0x0272,0x0131,
		   0x008c,0x004e,0x0027,0x0013};

然后就是广搜了, 用一个数组short isAdd[65535]来记录这个状态值是否已经搜索过, 同时记下搜索步骤step

如果得到了0(全白)或65535(全黑), 则搜索成功, 返回step

如果队列Que为空, 则表示不可能"Impossible", 返回-1

#include<iostream>
#include<deque>
using namespace std;
deque<int> Que;
short isAdd[65535];
int dir[]={0xc800,0xe400,0x7200,0x3100,
   		   0x8c80,0x4e40,0x2720,0x1310,
		   0x08c8,0x04e4,0x0272,0x0131,
		   0x008c,0x004e,0x0027,0x0013};

int bfs()
{
	int i,t1,t2,tmp,sum=1,step=0;
	while(!Que.empty())
	{
		step++;
		tmp=sum;
		sum=0;
		while(tmp--)
		{
			t1=Que.front();
			for(i=0;i<16;i++)
			{
				t2=t1^dir[i];
				if(!isAdd[t2])
				{
					Que.push_back(t2);
					isAdd[t2]=1;
					sum++;
				}
			}
			Que.pop_front();
			if(isAdd[0]==1 || isAdd[65535]==1)
				return step;
		}
	}
	return -1;
}
int main()
{
	int i,tmp;
	char c[17];
	while(scanf("%s",c)!=EOF)
	{
		Que.clear();
		memset(isAdd,0,sizeof(isAdd));
		for(i=1;i<4;i++)
			scanf("%s",c+(i*4));
		tmp=0;
		for(i=0;i<16;i++)
			if(c[i]=='b')
				tmp+=1<<i;
		Que.push_back(tmp);
		isAdd[tmp]=1;
		if(tmp==0 || tmp==65535)
			puts("0");
		else
		{
			int ret=bfs();
			if(ret==-1)
				puts("Impossible");
			else
				printf("%d/n",ret);
		}
	}
	return 0;
}

ps:我的英语啊-_-....比Google翻译(文章)还差