题解
【入门】骑士的拯救行动
1 条题解
-
0
#include<bits/stdc++.h> using namespace std; char s; // q1,q2:骑士r坐标;z1,z2:公主a坐标 // d数组:d[i][j]存走到(i,j)的最小耗时;a地图存格子类型;m,n行列;f无用变量 int q1,q2,z1,z2,d[25][25],m,n,a[25][25],f; // 方向数组 fx[0],fy[0]闲置,1~4对应:右、下、左、上四个移动方向 int fx[10]={0,0,1,0,-1}; int fy[10]={0,1,0,-1,0}; void dfs(int x,int y,int z){ // 如果当前格子是守卫x(a[x][y]==1),击杀守卫+1耗时 if(a[x][y]==1){ z++; } //如果当前走到(x,y)的时间z >= 之前记录的最优时间,这条路更差,不用继续搜 if(z<d[x][y]){ d[x][y]=z; // 更新该点最短耗时 // 遍历四个移动方向 for(int i=1;i<=4;i++){ int tx=x+fx[i]; // 新x坐标 int ty=y+fy[i]; // 新y坐标 //可以走(0道路/公主,1守卫,2是墙壁#不能走) if(a[tx][ty]<=1){ dfs(tx,ty,z+1); // 移动一步+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]=2; // 墙壁:2,不能通行 }else if(s=='r'){ q1=i; q2=j; // 骑士起点坐标记录 }else if(s=='a'){ z1=i; z2=j; // 公主终点坐标记录 }else if(s=='x'){ a[i][j]=1; // 守卫:1,经过要多花1点时间 } // 剩下'@'道路默认a[i][j]=0,无需赋值 } } dfs(q1,q2,1); // 从骑士起点开始搜索,初始z=1(起点本身占1单位,最后要-1修正) // 终点还是无穷大:无法到达 if(d[z1][z2]==INT_MAX){ cout<<"Impossible"; }else{ cout<<d[z1][z2]-1; // 起点初始多算1,输出减1修正答案 } return 0; }
- 1