题解
采药
1 条题解
-
0
#include<bits/stdc++.h> using namespace std; char s; int q1,q2,z1,z2,d[50][50],m,n,a[50][50]; int fx[9]={0,0,1,0,-1}; int fy[9]={0,1,0,-1,0}; // 深度优先搜索函数,用于寻找从起点到终点的最短路径 // x, y 为当前位置坐标,z 为当前走过的方格数 void dfs(long long x,long long y,long long z){ // 如果当前路径到达该点的步数更少,则更新最短路径 d[x][y]=z; int tx,ty; // 尝试向四个方向移动 for(int i=1;i<=4;i++){ tx=x+fx[i]; ty=y+fy[i]; // 如果移动后的位置没有怪物且在地图范围内 if(a[tx][ty]==0&&z+1<d[tx][ty]){ dfs(tx,ty,z+1); // 继续搜索 } } } int main(){ cin>>n>>m; // 初始化距离数组为极大值,表示初始时所有位置都不可达 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ d[i][j]=INT_MAX; cin>>s; // 处理输入的地图信息 if(s=='#'){ a[i][j]=1; // 标记为怪物格 }else if(s=='@'){ q1=i; q2=j; // 记录起点位置 }else if(s=='*'){ z1=i; z2=j; // 记录终点位置 } } } // 从起点开始深度优先搜索 dfs(q1,q2,1); // 输出结果,如果终点可达则输出最短路径长度,否则输出-1 if(d[z1][z2]!=INT_MAX){ cout<<d[z1][z2]-1; }else{ cout<<-1; } return 0; }
- 1