FJUT 1284 POJ 3984 迷宫问题 bfs

迷宫问题 bfs"/>

FJUT 1284 POJ 3984 迷宫问题 bfs

迷宫问题

TimeLimit:1000MS MemoryLimit:65536MB
64-bit integer IO format:%lld
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
左上角到右下角的最短路径，格式如样例所示。 (逗号后面有一个空格。。。 我成功贡献了一次PE)
SampleInput
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
SampleOutput
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
一题经典的迷宫问题，广度优先搜索 在迷宫问题中 就是将相同的步数的情况（即 树中的同一深度）压入队列中 并且再将已经压入队列情况中引申出的情况也一并压入队列中 直至找到答案 并用数组来记录路径 最后输出答案。接下来献上我的low b代码

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
char maps[10][10],vis[10][10],moves[4][2]={-1,0,1,0,0,1,0,-1};//存地图 标记是否来过 方向
struct node
{int x,y;
};
node p,q,r,temp;// p，q为起点和终点
void bfs()
{node pre[10][10],way[105];//pre数组记录路径 way保存答案queue<node>que;que.push(p);//先压入起点int top;while(!que.empty())//当队列中不存在元素时 则为结束条件{r=que.front();que.pop();//取出点后弹出if(r.x==q.x&&r.y==q.y)//判断是否为终点 如果是则输出答案{top=0;while(1){way[top++]=r;if(r.x==p.x&&r.y==p.y)//回溯到起点时结束break;r=pre[r.x][r.y];}while(top--){printf("(%d, %d)\n",way[top].x-1,way[top].y-1);}}for(int i=0;i<4;i++)//从已在队列中存在的点分散出的情况{temp.x=r.x+moves[i][0];temp.y=r.y+moves[i][1];if(!maps[temp.x][temp.y]&&!vis[temp.x][temp.y])//判断是否符合条件 符合则压入队列{pre[temp.x][temp.y]=r;vis[temp.x][temp.y]=1;que.push(temp);}}}
}
main()
{p.x=p.y=1;q.x=q.y=5;memset(maps,1,sizeof(maps));//将迷宫设置为全部为墙的情况（清空）for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)scanf("%d",&maps[i][j]);bfs();
}

总结 bfs算是一种经典且基础的算法 应该多回顾 多总结不同情况 就会变得娴熟 感谢各位大佬的观看 有错误的地方还望指正