1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] n-迷阵的行数,m-迷阵的列数(全程使用0-based数组坐标) int n,m; // [2] arr数组-存储迷阵地图,字符含义:@起点、.可通行区域、*终点、#不可通行障碍 char arr[100][100]; // [3] dp数组-存储各坐标到起点的累计步数,初始化为INT_MAX表示「暂未访问/不可达」 int dp[100][100]; // [4] 四个方向偏移量(左、下、右、上),覆盖所有可移动的相邻方向 int dx[4]={0,1,0,-1}; int dy[4]={-1,0,1,0}; // [5] a,b-起点@的0-based坐标;c,d-终点*的0-based坐标 int a,b,c,d; // [6] DFS递归函数:从当前坐标出发遍历所有可达路径,更新各点到起点的步数 // 参数说明:x-当前位置横坐标 | y-当前位置纵坐标 | len-从起点到当前位置的累计步数 void dfs(int x,int y,int len){ // [7] 记录当前坐标的步数,更新为从起点到此处的累计步数 dp[x][y]=len;//把符合条件的数据存入dp中 // [8] 递归终止条件:到达终点*,直接返回(不再继续探索后续路径) if(x==c && y==d) return; // [9] 遍历四个方向,尝试向相邻位置扩展路径 for(int i=0;i<4;i++){ // [10] 计算相邻位置的横坐标和纵坐标 int tx=x+dx[i]; int ty=y+dy[i]; // [11] 路径合法性综合判断,满足所有条件才继续递归: // (1) 坐标在迷阵合法范围内 (2) 相邻位置是可通行区域(.普通区域/*终点) (3) 新路径步数更短(剪枝,避免无效递归和重复更新) if((tx>=0 && tx<n) && (ty>=0 && ty<m) && (arr[tx][ty]=='.' || arr[tx][ty]=='*') && len+1 < dp[tx][ty]){ // [12] 相邻位置可通行,步数+1,继续递归探索下一个位置 dfs(tx,ty,len+1); } } } int main(){ // [13] 读取迷阵的行数n和列数m cin>>n>>m; // [14] 遍历迷阵,读取地图数据并完成初始化 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>arr[i][j]; // [15] 读取当前坐标的地图字符 dp[i][j]=INT_MAX; // [16] 初始化所有位置步数为INT_MAX(暂未访问/不可达) if(arr[i][j]=='@'){ // [17] 记录起点@的0-based坐标 a=i,b=j; } if(arr[i][j]=='*'){ // [18] 记录终点*的0-based坐标 c=i,d=j; } } } // [19] 从起点开始DFS探索,初始累计步数为0 dfs(a,b,0); // [20] 结果判断与输出:终点可达则输出累计步数,不可达则输出-1 if(dp[c][d]!=INT_MAX) cout<<dp[c][d]; else cout<<-1; return 0; }
- 1
信息
- ID
- 1300
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 31
- 已通过
- 2
- 上传者