目录
POJ3984迷宫问题题目描述思路分析代码
POJ3984迷宫问题
日常安利本题我的博客
题目描述
给出一个5×5的数字矩阵其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
思路分析
事实证明，bfs对这种数字矩阵的处理能力明显不如dfs，bfs对距离矩阵的处理更强。 之前对图的处理多是那种邻接矩阵的处理，但是对这种数字矩阵的处理要差很多，刚开始做法大体是知道，但是编程时却有点蒙，基础太差了。 首先，回忆一下bfs。bfs就是广度优先搜索，从起始点开始，将这个点相连的点加入到队列之中，标记经过的点，然后依次将队列中的点取出，然后加入与这个点相连的点（要并未访问过的），因为队列先进先出的规律，所以就可以分层次遍历途中所有点。这里值得注意的是，由于是从开始分层遍历，所以先经过的点一定是最优的。即如果某个点是最短路的必经之路，那么第一次访问它的前一个节点也一定是必经之路。通过这个特点，就可以在将点加入队列的时候，顺便记录一下他的父亲节点（即这个节点的上一个节点）。这样通过队最后一个节点开始递归，就可以找到最短路径了。 记录路径时，因为这个图只有上下左右四个方向，所以可以通过方向记录，空间上这么做更为优秀，但是为了之后处理距离矩阵的图，所以用struct数组存点的路径。另外我的代码并没有采用递归，而是使用差不多的栈结构。在路径比较长时，可以使用vector代替，但是本题不需要，我就懒着了吧_。
代码
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<string>
#include <stack>
#include<queue>
using namespace std ;
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
const double eps = 1e-8;
const int maxn = 110010;//须填写
const int inf = 0x3f3f3f3f;
int dir[4][2]={
0,-1, //up
0,1, //down
-1,0, //left
1,0, //rights
};
int vis[10][10];
int pic[10][10];
struct Node
{
int x;
int y;
};
Node way[10][10];
void bfs(Node node)
{
queue <Node> que;
Node n;
int x,y;
que.push(node);
vis[node.x][node.y]=1;
way[node.x][node.y].x=-1;
while(!que.empty())
{
n=que.front();
que.pop();
for(int i=0;i<4;i++)
{
x=n.x+dir[i][0];
y=n.y+dir[i][1];
if(x>=0&&x<5&&y>=0&&y<5&&pic[x][y]==0&&vis[x][y]==0)
{
way[x][y]=n;
n.x=x;
n.y=y;
vis[x][y]=1;
que.push(n);
}
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
scanf("%d",&pic[i][j]);
}
}
Node node;
stack<Node> s;
node.x=0;
node.y=0;
bfs(node);
node.x=4;
node.y=4;
while(node.x!=-1)
{
s.push(node);
node=way[node.x][node.y];
}
while(!s.empty())
{
node=s.top();
printf("(%d, %d)\n",node.x,node.y);
s.pop();
}
return 0;
}
