top1编程
← 返回题目
题解

【入门】骑士的拯救行动

1 条题解

  • 0
    @ 2026-7-28 22:10:02
    #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