1 条题解
-
0
#include <bits/stdc++.h> using namespace std; // [1] n-迷宫的行数;m-迷宫的列数 int n,m; // [2] arr数组-存储迷宫地图,0表示可走,1表示不可走/已访问 int arr[200][200]; // [3] q_x,q_y-起点坐标(0-based);z_x,z_y-终点坐标(0-based) int q_x,q_y,z_x,z_y; // [4] 四个方向的偏移量(右、下、左、上) int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; // [5] 队列存储的坐标结构体(用于BFS遍历节点) struct qtu{ int x,y; }; // [6] 栈存储的坐标结构体(用于回溯路径) struct vtu{ int v_x,v_y; }; // [7] 前驱坐标结构体(存储每个节点的父节点坐标,用于回溯路径) struct stu{ int s_x,s_y; }brr[200][200]; // [8] brr数组-记录每个节点的前驱坐标 queue<qtu> q; // [9] BFS队列,存储待处理的节点坐标 stack<vtu> v; // [10] 路径栈,存储回溯后的路径坐标 void bfs(){ // 1. BFS初始化:起点入队,标记为已访问,设置起点前驱为-1(无父节点) q.push({q_x,q_y}); arr[q_x][q_y]=1; // [11] 标记起点为已访问(避免重复入队) brr[q_x][q_y]={-1,-1}; // [12] 起点无前驱,设为-1,-1 // 2. 处理队列中的节点(BFS核心循环) while(!q.empty()){ qtu a=q.front(); q.pop(); // [13] 取出队首节点 // 5. 判断是否到达终点:如果当前节点是终点,回溯路径并输出 if(a.x==z_x && a.y==z_y){ // 6. 回溯路径:从终点倒推到起点,存入栈中(栈的先进后出特性可让路径正序输出) int i=z_x,j=z_y; while(i!=-1 && j!=-1){ v.push({i,j}); // [14] 当前节点入栈 // 获取当前节点的前驱坐标,继续倒推 int a=brr[i][j].s_x; int b=brr[i][j].s_y; i=a; j=b; } // 7. 输出路径:从栈顶依次弹出(正序输出路径) while(!v.empty()){ int a=v.top().v_x; int b=v.top().v_y; v.pop(); // 输出1-based坐标(题目输入输出为1-based,代码处理为0-based,需转换) cout<<"("<<a+1<<","<<b+1<<")"; if(!v.empty()) cout<<"->"; // [15] 非最后一个节点输出箭头连接 } return; } // 3. 遍历四个方向,扩展当前节点的邻居 for(int i=0;i<4;i++){ int tx=a.x+dx[i]; // [16] 计算新节点的横坐标 int ty=a.y+dy[i]; // [17] 计算新节点的纵坐标 // 判断新节点是否在迷宫范围内,且未被访问(arr[tx][ty]==0) if((tx>=0 && tx<n) && (ty>=0 && ty<m) && arr[tx][ty]==0){ arr[tx][ty]=1; // [18] 标记新节点为已访问 q.push({tx,ty}); // [19] 新节点入队 // 4. 记录新节点的前驱坐标(当前节点a是新节点的父节点) brr[tx][ty].s_x=a.x; brr[tx][ty].s_y=a.y; } } } // 8. 队列处理完毕仍未找到终点,输出"no way" cout<<"no way"; } int main(){ cin>>n>>m; // [20] 读取迷宫的行数n和列数m // 读取迷宫地图 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>arr[i][j]; } } // 读取起点和终点坐标(输入为1-based,转换为0-based) cin>>q_x>>q_y>>z_x>>z_y; q_x-=1,q_y-=1,z_x-=1,z_y-=1; // [21] 1-based转0-based,适配代码中的坐标处理 bfs(); // [22] 调用BFS寻找最短路径 return 0; }
- 1
信息
- ID
- 1310
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 6
- 已通过
- 1
- 上传者