迷宫问题

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 46 Accepted Submission(s) : 28

Problem Description

定义一个二维数组：

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

/*将表格排序，第一行为0,1,2,3,4第二行5,6,7,8,9，规则就是5*横坐标+纵坐标，得到的数除以五

得到横坐标，对五取余得到纵坐标，用数组的下标来记录这些数，数组里记录上一个数的下标，

方便查找，而第一个数存的是-1，表示结束*/

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

int map[5][5],vis[30],pre[30];

int dx[4]={1,0,0,-1};

int dy[4]={0,1,-1,0};

void pr(int ans)

{

	/*for(int i=0;i<30;i++)

	printf("%d \n",pre[i]);*/

	if(pre[ans]!=-1)/*从终点往回找，找到起点时开始输出*/

		pr(pre[ans]);

		printf("(%d, %d)\n",ans/5,ans%5);

}

int judge(int x,int y)

{

	if(x<0||x>4||y<0||y>4)

	return 0;

	if(map[x][y]==1)

	return 0;

	return 1;

}

void bfs()

{

	queue<int>q;

	memset(vis,0,sizeof(vis));

	pre[0]=-1;

	vis[0]=1;/*标记已经使用过*/

	q.push(0);

	int now,next;

	int x,y,nx,ny;

	while(!q.empty())

	{

		now=q.front();

		q.pop();

		x=now/5;/*调用坐标*/

		y=now%5;

		for(int i=0;i<4;i++)

		{

			nx=x+dx[i];

			ny=y+dy[i];

			next=nx*5+ny;

			if(judge(nx,ny)&&!vis[next])

			{

				pre[next]=now;

				if(next==24)

				return ;/*当查询到最后一个点时，结束*/

				q.push(next);

				vis[next]=1;

			}

		}

	}

}

int main()

{

	int i,j;

	for(i=0;i<5;i++)

	for(j=0;j<5;j++)

	scanf("%d",&map[i][j]);

	/*for(i=0;i<5;i++)

	{

		for(j=0;j<5;j++)

		printf("%d ",map[i][j]);

		printf("\n");

	}/*输出一遍表，看有没有输入错误*/

	bfs();

	pr(24);/*从最后一个点往回找*/

	return 0;

}

巴特西

hdoj--迷宫问题

迷宫问题

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 46 Accepted Submission(s) : 28

最新文章

热门文章