位置： 首页 > 活动 > > 详情

新消息丨11.迷宫问题(BFS 储存路径)

来源：博客园    2023-05-02 19:28:57


【资料图】

迷宫问题

↑ 题目链接

题目

给定一个 \(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<

标签：

最近更新

资讯

景点

  • 路线
河南新增本土无症状感染者23例
天津新增本土确诊病例10例、本土无症状感染者8例

Copyright ©  2015-2022 北冰洋频旅游网版权所有  备案号：沪ICP备2020036824号-3   联系邮箱：562 66 29@qq.com