top1编程
← 返回题目
题解

【提高】小H回家

1 条题解

  • 0
    @ 2026-7-29 0:18:14
    #include<bits/stdc++.h>
    using namespace std;
    const int N=10,M=10;
    int n,m;
    int g[N][M];
    int sx,sy,ex,ey;
    int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    struct Node{
        int x,y,hp,time;
    };
    bool vis[N][M][7];
    int bfs(){
        queue<Node>q;
        q.push({sx,sy,6,0});
        vis[sx][sy][6]=true;
        while(!q.empty()){
            Node u=q.front();
            q.pop();
            if(u.x==ex&&u.y==ey)return u.time;
            for(int i=0;i<4;i++){
                int nx=u.x+dir[i][0];
                int ny=u.y+dir[i][1];
                int nhp=u.hp-1;
                int ntime=u.time+1;
                if(nx<1||nx>n||ny<1||ny>m)continue;
                if(g[nx][ny]==0)continue;
                if(nhp==0)continue;
                if(g[nx][ny]==4)nhp=6;
                if(vis[nx][ny][nhp])continue;
                vis[nx][ny][nhp]=true;
                q.push({nx,ny,nhp,ntime});
            }
        }
        return -1;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                scanf("%d",&g[i][j]);
                if(g[i][j]==2){
                    sx=i;
                    sy=j;
                }else if(g[i][j]==3){
                    ex=i;
                    ey=j;
                }
            }
        int ans=bfs();
        printf("%d",ans);
        return 0;
    }
    
    • 1