我很水,第一次写图的算法,在网上看了下广度搜索,然后就写了这个很搓很搓的程序.至于说搓到什么程度!!!题目中的测试数据我跑了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;
}

• Re:我很水,第一次写图的算法,在网上看了下广度搜索,然后就写了这个很搓很搓的程序.至于说搓到什么程度!!!题目中的测试数据我跑了1分多钟才跑出结果.可以输出每一步的结果,答案是对的. (6028) 20132430120 2015-05-27 22:55:15