bfs.cpp

ACM入门题,BFS + hash 的使用与结合

#include<stdio.h>
#include<string.h>

char pos[2<<17];

int quene[2<<17];
int move[4][2] = {1,0,-1,0,0,1,0,-1};
int test[4][4]= 
{
	0x00000001,0x00000002,0x00000004,0x00000008,
	0x00000010,0x00000020,0x00000040,0x00000080,
	0x00000100,0x00000200,0x00000400,0x00000800,
	0x00001000,0x00002000,0x00004000,0x00008000
};

int BFS(int from,int to)
{
	int x,y,num,tnum;
	int i,j,k,len,step,tlen;
	
	len = 1;
	i = step = 0;
	quene[0] = from;

	while(i<len)
	{
		step++;
		tlen = len;
		for(;i < tlen; i++)
		{
			num = quene[i];
			if(quene[i] == to) return step;
			
			for(j = 0;j < 16;j++)
			{
				x = j/4;
				y = j%4;
				
				for(k=0;k<4;k++)
				{
					if(x+move[k][0] >=0 && x+move[k][0] < 4
						&& y+move[k][1] >=0 && y+move[k][1] < 4
						&& (test[x][y]&num) != (test[x+move[k][0]][y+move[k][1]]&num)
						)
					{
						tnum = num;
						tnum = tnum&test[x][y]?(~test[x][y])&tnum:(test[x][y])|tnum;
						tnum = tnum&test[x+move[k][0]][y+move[k][1]]?
							(~test[x+move[k][0]][y+move[k][1]])&tnum:
						(test[x+move[k][0]][y+move[k][1]])|tnum;
						
						if(pos[tnum] == 0)
						{
							quene[len++] = tnum;
							pos[tnum] = 1;
						}
					}
				}
			}
		}
	}
	return 0;
}


int main()
{
	char temp[8];
	int from,to,m,n;
	while(1)
	{
		from = to = 0;
		memset(pos,0,sizeof(char)*(65536+8));
		for(m=0;m<4;m++)
		{
			if(scanf("%s",temp)==EOF) 
				return 0;
			for(n=0;n<4;n++)
				from = from|((temp[n] == '1')?test[m][n]:0);
		}
		for(m=0;m<4;m++)
		{
			scanf("%s",temp);
			for(n=0;n<4;n++)
				to = to|((temp[n] == '1')?test[m][n]:0);
		}
		printf("%d\n",BFS(from,to) - 1);
	}
	return 0;
}