poj3984 迷宫问题 简单bfs打印路径

题目传送门：poj 3984 迷宫问题
这个是中文题目，是很好理解的。
这也是一道很好的bfs模板题目。

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<iostream>
using namespace std;
struct Node{
int x;
int y;
int step;
//这个是用来保存当前到达了那个位置
int state[50];
//这个是记录当前状态向下一个状态装换的时候的方向
};
int dirX[4] = {1,0,0,-1};
int dirY[4] = {0,1,-1,0};
int maze[6][6];
bool vis[10][10];
Node bfs()
{
memset(vis,false,sizeof(vis));
queue<Node>q;
Node next;
Node cur;
cur.x = 0;
cur.y = 0;
cur.step = 0;
q.push(cur);
vis[0][0] = true;
while(!q.empty())
{
cur = q.front();
q.pop();
if(cur.x == 4 && cur.y == 4)
return cur;
for(int i=0;i<4;i++)
{
int tempX = dirX[i] + cur.x;
int tempY = dirY[i] + cur.y;
if(tempX <0 || tempX>4 || tempY <0 || tempY>4 || vis[tempX][tempY] || maze[tempX][tempY]==1)
continue;
vis[tempX][tempY]
=true;
next = cur;
//使前后几个步骤连接起来，当前指向下一个
next.x = tempX;
next.y = tempY;
next.step = cur.step + 1;
next.state[cur.step] = i; //记录到达这个步骤的状态
q.push(next);
}
}
return cur;
}
int main()
{
int i,j;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&maze[i][j]);
Node ans = bfs();
int x = 0;
int y=0;
for(i=0;i<=ans.step;i++)
{
printf("(%d, %d)n",x,y);
if(i!=ans.step)
//为了确保最后不是加的空值
{
x+=dirX[ans.state[i]];
y+=dirY[ans.state[i]];
}
}
return 0;
}

最后

以上就是冷酷羊为你收集整理的poj3984 迷宫问题 简单bfs打印路径的全部内容，希望文章能够帮你解决poj3984 迷宫问题 简单bfs打印路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。