> 我很水,第一次写图的算法,在网上看了下广度搜索,然后就写了这个很搓很搓的程序.至于说搓到什么程度!!!题目中的测试数据我跑了1分多钟才跑出结果.可以输出每一步的结果,答案是对的.
> 
> 
> #include <stdio.h>
> #include <string.h>
> 
> struct GRAPH
> {
> 	int g[3][3];
> 	int oi,oj;
> 
> 	int father;
> 	char path;
> };
> 
> struct QUEUE
> {
> 	GRAPH node[362881];
> 	int top;
> };
> 
> char paths[100];
> GRAPH final;
> QUEUE queue;
> 
> int eque(GRAPH g1,GRAPH g2)
> {
> 	int i,j;
> 	if(g1.oi != g2.oi || g1.oj != g2.oj)
> 		return 0;
> 	else
> 	{
> 		for(i=0;i<3;i++)
> 			for(j=0;j<3;j++)
> 				if(g1.g[i][j] != g2.g[i][j])
> 					return 0;
> 	}
> 	return 1;
> }
> 
> int move(GRAPH graph,int n)
> {
> 	GRAPH temp[4];
> 	int num;
> 	int i,j,k,m;
> 	for(i=0;i<4;i++)
> 	{
> 		temp[i] = graph;
> 		temp[i].father = n;
> 	}
> 	if(graph.oi == 0 && graph.oj==0)
> 	{
> 		temp[0].g[0][0] = temp[0].g[0][1];
> 		temp[0].g[0][1] = 0;
> 		temp[0].oj=1;
> 		temp[0].path = 'r';
> 
> 		temp[1].g[0][0] = temp[1].g[1][0];
> 		temp[1].g[1][0] = 0;
> 		temp[1].oi = 1;
> 		temp[1].path = 'd';
> 		num = 2;
> 	}
> 	else if(graph.oi ==0 && graph.oj==1)
> 	{
> 		temp[0].g[0][1] = temp[0].g[0][0];
> 		temp[0].g[0][0] = 0;
> 		temp[0].oj=0;
> 		temp[0].path = 'l';
> 
> 		temp[1].g[0][1] = temp[1].g[0][2];
> 		temp[1].g[0][2] = 0;
> 		temp[1].oj = 2;	
> 		temp[1].path = 'r';
> 
> 		temp[2].g[0][1] = temp[2].g[1][1];
> 		temp[2].g[1][1] = 0;
> 		temp[2].oi = 1;
> 		temp[2].path = 'd';
> 		num = 3;
> 	}
> 	else if(graph.oi ==0 && graph.oj==2)
> 	{
> 		temp[0].g[0][2] = temp[0].g[0][1];
> 		temp[0].g[0][1] = 0;
> 		temp[0].oj=1;
> 		temp[0].path = 'l';
> 
> 		temp[1].g[0][2] = temp[1].g[1][2];
> 		temp[1].g[1][2] = 0;
> 		temp[1].oi = 1;	
> 		temp[1].path = 'd';
> 		num = 2;
> 	}
> 	else if(graph.oi == 1 && graph.oj==0)
> 	{
> 		temp[0].g[1][0] = temp[0].g[0][0];
> 		temp[0].g[0][0] = 0;
> 		temp[0].oi=0;
> 		temp[0].path = 'u';
> 
> 		temp[1].g[1][0] = temp[1].g[2][0];
> 		temp[1].g[2][0] = 0;
> 		temp[1].oi = 2;
> 		temp[1].path = 'd';
> 
> 		temp[2].g[1][0] = temp[0].g[1][1];
> 		temp[2].g[1][1] = 0;
> 		temp[2].oj=1;
> 		temp[2].path = 'r';
> 		num = 3;
> 	}
> 	else if(graph.oi == 1 && graph.oj==1)
> 	{
> 		temp[0].g[1][1] = temp[0].g[0][1];
> 		temp[0].g[0][1] = 0;
> 		temp[0].oi=0;
> 		temp[0].path = 'u';
> 
> 		temp[1].g[1][1] = temp[1].g[1][0];
> 		temp[1].g[1][0] = 0;
> 		temp[1].oj = 0;
> 		temp[1].path = 'l';
> 
> 		temp[2].g[1][1] = temp[0].g[1][2];
> 		temp[2].g[1][2] = 0;
> 		temp[2].oj=2;
> 		temp[2].path = 'r';
> 
> 		temp[3].g[1][1] = temp[0].g[2][1];
> 		temp[3].g[2][1] = 0;
> 		temp[3].oi=2;
> 		temp[3].path = 'd';
> 		num = 4;
> 	}
> 	else if(graph.oi == 1 && graph.oj==2)
> 	{
> 		temp[0].g[1][2] = temp[0].g[0][2];
> 		temp[0].g[0][2] = 0;
> 		temp[0].oi=0;
> 		temp[0].path = 'u';
> 
> 		temp[1].g[1][2] = temp[1].g[2][2];
> 		temp[1].g[2][2] = 0;
> 		temp[1].oi = 2;
> 		temp[1].path = 'd';
> 
> 		temp[2].g[1][2] = temp[0].g[1][1];
> 		temp[2].g[1][1] = 0;
> 		temp[2].oj=1;
> 		temp[2].path = 'l';
> 		num = 3;
> 	}
> 	else if(graph.oi ==2 && graph.oj==0)
> 	{
> 		temp[0].g[2][0] = temp[0].g[1][0];
> 		temp[0].g[1][0] = 0;
> 		temp[0].oi=1;
> 		temp[0].path = 'u';
> 
> 		temp[1].g[2][0] = temp[1].g[2][1];
> 		temp[1].g[2][1] = 0;
> 		temp[1].oj = 1;	
> 		temp[1].path = 'r';
> 		num = 2;
> 	}
> 	else if(graph.oi == 2 && graph.oj==1)
> 	{
> 		temp[0].g[2][1] = temp[0].g[2][0];
> 		temp[0].g[2][0] = 0;
> 		temp[0].oj=0;
> 		temp[0].path = 'l';
> 
> 		temp[1].g[2][1] = temp[1].g[2][2];
> 		temp[1].g[2][2] = 0;
> 		temp[1].oj = 2;
> 		temp[1].path = 'r';
> 
> 		temp[2].g[2][1] = temp[0].g[1][1];
> 		temp[2].g[1][1] = 0;
> 		temp[2].oi=1;
> 		temp[2].path = 'u';
> 		num = 3;
> 	}
> 	else if(graph.oi == 2 && graph.oj==2)
> 	{
> 		temp[0].g[2][2] = temp[0].g[2][1];
> 		temp[0].g[2][1] = 0;
> 		temp[0].oj=1;
> 		temp[0].path = 'l';
> 
> 		temp[1].g[2][2] = temp[1].g[1][2];
> 		temp[1].g[1][2] = 0;
> 		temp[1].oi = 1;
> 		temp[1].path = 'u';
> 		num = 2;
> 	}
> 	if(queue.top == 362881)
> 	{
> 		printf("exit!!!\n");
> 		return 0;
> 	}
> 	int preTop = queue.top;
> 	
> 	for(k=0;k<num;k++)
> 	{
> 		for(m=0;m<queue.top;m++)
> 			if(eque(temp[k],queue.node[m])==1)
> 				break;
> 		if(m==queue.top)
> 			queue.node[queue.top++] = temp[k];
> 	}
> 	for(k=preTop;k<queue.top;k++)
> 	{
> 		if(eque(queue.node[k],final))
> 		{
> 			int p=0;
> 			while(queue.node[k].father != -1)
> 			{
> 		/*		for(i=0;i<3;i++)
> 				{
> 					for(j=0;j<3;j++)
> 						printf("%d ",queue.node[k].g[i][j]);
> 					printf("\n");
> 				}
> 				printf("\n");*/
> 				paths[p++] = queue.node[k].path;
> 				queue.node[k] = queue.node[queue.node[k].father];
> 			}
> 			return 1;
> 		}
> 	}
> 
> 	return 0;
> }
> //2  3  4  1  5  x  7  6  8
> //1  2  3  x  4  6  7  5  8
> int pop()
> {
> 	int i;
> 	for(i=0;i<queue.top-1;i++)
> 		queue.node[i] = queue.node[i+1];
> 	queue.top--;
> 
> 	return 1;
> }
> 
> bool BFS()
> {
> 	int i=0;
> 	while(i >=0 && i <362881 && i<queue.top)
> 	{
> 		if(move(queue.node[i],i))
> 		break;
> 		i++;
> 	}
> 	return true;
> }
> 
> int main()
> {
> 	int i,j,k=1;
> 	char s[10];
> 	for(i=0;i<3;i++)
> 		for(j=0;j<3;j++)
> 			final.g[i][j] = k++;
> 	final.g[2][2] =0;
> 	final.oi = 2;
> 	final.oj = 2;
> 	GRAPH graph;
> 	for(i=0;i<9;i++)
> 	{
> 		scanf("%c",&s[i]);
> 		if(i<8)
> 		{
> 			getchar();
> 			getchar();
> 		}
> 		if(s[i]=='x')
> 		{
> 			s[i] = '0';
> 			graph.oi = i/3;
> 			graph.oj = i%3;
> 					
> 		}
> 		graph.g[i/3][i%3] = s[i]-'0';
> 	}
> 	graph.father = -1;
> 	queue.node[0] = graph;
> 	queue.top = 1;
> /*	for(i=0;i<3;i++)
> 	{
> 		for(j=0;j<3;j++)
> 			printf("%d ",final.g[i][j]);
> 		printf("\n");
> 	}
> 	printf("\n");*/
> 	BFS();
> 	int len = strlen(paths);
> 	for(i=len-1;i>=0;i--)
> 		printf("%c",paths[i]);
> 	printf("\n");
> 	return 0;
> }