最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

11.迷宫问题(BFS 储存路径)

来源：博客园


(资料图片仅供参考)

迷宫问题

↑ 题目链接

题目

给定一个 \(n×n\) 的二维数组，如下所示：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式

第一行包含整数 \(n\)。接下来 \(n\) 行，每行包含 \(n\) 个整数 \(0\) 或 \(1\)，表示迷宫。

输出格式

输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 \((0,0)\) ，右下角坐标为 \((n−1,n−1)\)

数据范围

$ 0≤n≤1000$

输入样例：

50 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

输出样例：

0 01 02 02 12 22 32 43 44 4

思路

从终点往起点 \(BFS\) 搜索，第一次到达时保存路径，最后输出

代码

#include#define x first#define y secondusing namespace std;typedef pairPII;const int N=1010;int g[N][N];bool st[N][N];PII pre[N][N];int dx[]={-1,0,1,0},dy[]={0,1,0,-1};int n;void bfs(){queueq;q.push({n-1,n-1});st[n-1][n-1]=true;while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int a=t.x+dx[i],b=t.y+dy[i];if(a<0||a>=n||b<0||b>=n||st[a][b]||g[a][b]==1)continue;pre[a][b]={t.x,t.y};//保存路径st[a][b]=true;q.push({a,b});}}}int main(){cin>>n;for(int i=0;i>g[i][j];bfs();int x=0,y=0;while(1){    cout<

关键词：