1 条题解
-
0
#include <bits/stdc++.h> using namespace std; // [1] 定义坐标结构体,a表示行坐标,b表示列坐标 struct stu{ int a,b; }; // [2] 路径存储数组,按访问顺序保存从起点到当前点的所有坐标 vector<stu> arr; // [3] 迷宫的行数和列数 int n,m; // [4] 迷宫地图存储数组,crr[i][j]表示第i行第j列的格子状态('o'可走/'#'不可走) char crr[110][110]; // [5] 访问标记数组,flag[i][j]=1表示坐标(i,j)已访问,避免重复走 int flag[110][110]={}; // [6] 方向偏移量数组,严格遵循题目策略顺序:右→下→左→上 int dx[4]={0,1,0,-1}; // [7] 对应dx的列方向偏移量,与dx一一对应 int dy[4]={1,0,-1,0}; // [8] 有效路径计数变量,记录找到的路径序号,初始为0 int sum=0; // [16] 深度优先搜索(DFS)核心函数,参数x为当前行坐标,y为当前列坐标 void dfs(int x,int y){ // [17] 递归终止条件:到达终点(n,m),输出当前有效路径 if(x==n && y==m){ sum++; // [18] 有效路径计数自增 cout<<sum<<":"<<arr[0].a<<","<<arr[0].b; // [19] 输出路径序号和起点坐标 // [20] 循环输出路径中后续的所有坐标节点 for(int i=1;i<arr.size();i++){ cout<<"->"<<arr[i].a<<","<<arr[i].b; // [21] 拼接输出路径节点,格式为「->行,列」 } cout<<endl; // [22] 换行分隔不同路径,保证输出整洁 return ; // [23] 递归返回,结束当前路径的后续搜索 } // [24] 按「右→下→左→上」的顺序尝试四个方向移动 for(int i=0;i<4;i++){ int tx=x+dx[i]; // [25] 计算下一个候选点的行坐标 int ty=y+dy[i]; // [26] 计算下一个候选点的列坐标 // [27] 候选点合法性判断:在迷宫范围内、未被访问、是可走的格子('o') if((tx>=1 && tx<=n) && (ty>=1 && ty<=m) && flag[tx][ty]==0 && crr[tx][ty]=='o'){ flag[tx][ty]=1; // [28] 标记候选点为已访问,防止重复遍历 arr.push_back({tx,ty}); // [29] 将候选点加入路径数组,记录当前路径 dfs(tx,ty); // [30] 递归调用DFS,搜索候选点出发的后续路径 arr.pop_back(); // [31] 路径回溯:弹出当前点,恢复上一步的路径状态 flag[tx][ty]=0; // [32] 标记回溯:取消候选点的已访问状态,恢复可遍历 } } } // [9] 主函数,程序执行入口 int main(){ cin>>n>>m; // [10] 输入迷宫的行数n和列数m // [11] 读入n行迷宫地图,每行m个字符 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>crr[i][j]; // [12] 读入第i行第j列的格子状态 } } flag[1][1]=1; // [13] 标记起点(1,1)为已访问,避免重复访问 arr.push_back({1,1}); // [14] 将起点坐标加入路径数组,初始化路径 dfs(1,1); // [15] 从起点(1,1)开始深度优先搜索,跳转至[16]开始注释DFS逻辑 // [33] 题目要求:无有效路径时输出"no",原有代码缺失此逻辑,此处补充 if(sum == 0) { cout << "no" << endl; } return 0; // [34] 程序正常执行完毕,返回终止状态码0 }
信息
- ID
- 1292
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者