top1编程
← 返回题目
题解

采药

1 条题解

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