POJ_3984迷宫问题（bfs基础题）

62 阅读 0 评论 41 点赞

我是靠谱客的博主感性老虎，最近开发中收集的这篇文章主要介绍POJ_3984迷宫问题（bfs基础题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

中文题干，不多说了.

解题思路：

先说一下dfs和bfs的区别.dfs是一条路搜到底，不能再往下了，就回溯一步，需要用到递归.

而bfs是是一层层展开，比如说从第一个数0开始搜，然后把和0直接连接的数比如1，2，3都搜出来，加入队列，然后再把和1直接连接的搜出来，比如4，加入队列；然后再搜和2直接连接的，依次往下.简单的说就是一层一层的搜，每一条路径的搜索进度都是一样的，因此需要用到队列的知识，不需要使用递归.

因此dfs适合那些求可行性路径数目的，而bfs适合求最短路径之类的（因为一旦搜到，就是最短）.

然后再说一下这题的解题思路，vis标记那些走过的点，map标记题目给出的那些不能走的点，queue是我们走过的点的队列，每个点需要保存自己的坐标和自己的上一个节点.一旦搜到我们想要的点，就立刻输出.

具体见代码.

#include <cstdio>
#include <cstring>

using namespace std;

int map[6][6]; //地图
int vis[6][6]; //判重
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

struct node{
	int x,y; //坐标
	int c;   //上一点 
}queue[6*6];

void print(int head)
{
	while(queue[head].c != -1)
	{
		print(queue[head].c);
		printf("(%d, %d)n",queue[head].x,queue[head].y);
		return;	
	}
	printf("(0, 0)n");
}

void bfs(int x,int y)
{
	int head = 0,tail = 1;
	int i;
	queue[0].x = 0;
	queue[0].y = 0;
	queue[0].c = -1;
	struct node now;
	
	while(head < tail)
	{
		if(queue[head].x == 4 && queue[head].y == 4)
		{
			print(head);
			return;
		}
		for(i = 0;i < 4;i++)
		{
			now.x = queue[head].x + dir[i][0];
			now.y = queue[head].y + dir[i][1];
			now.c = head;
			if(now.x >= 0 && now.x <= 4 && now.y >= 0 && now.y <= 5)
			{
				if(!vis[now.x][now.y] && !map[now.x][now.y])
				{
					vis[now.x][now.y] = 1;
					queue[tail] = now;
					tail++;
				}
			}
		}
		head++;
	}
}

int main()
{
	int i,j;
	for(i = 0;i < 5;i++)
	{
		for(j = 0;j < 5;j++)
		{
			scanf("%d",&map[i][j]);
		}
	}
	memset(vis,0,sizeof(vis));
	bfs(0,0);
	return 0;
}