求助 PAC76分 bfs
  • 板块P2802 回家
  • 楼主DrAlfred
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/4/3 13:09
  • 上次更新2023/10/28 04:46:09
查看原帖
求助 PAC76分 bfs
583610
DrAlfred楼主2022/4/3 13:09
//setworldspawn ~ ~ ~
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int x,y;
    node(int &a,int &b){
        x=a;
        y=b;
    }
};
const int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
int n,m,_map[10][10],sx,sy,ex,ey,ans[10][10];
inline bool ok(int &x,int &y){
    return (x>=1&&x<=n)&&(y>=1&&y<=m)&&(ans[x][y]==-1)&&(_map[x][y]!=0);
}
inline void bfs(int &x,int &y){
    queue<node> que;
    queue <int>  hp;
    que.push(node(x,y));
    hp.push(6);
    ans[x][y]=0;
    while(!(que.empty())){
        node last=que.front();
        int lhp=hp.front();
        hp.pop();
        que.pop();
        if(last.x==ex&&last.y==ey){
            break;
        }
        int lx=last.x,ly=last.y;
        for(int i=0;i<4;i++){
            int nx=lx+dx[i],ny=ly+dy[i];
            int nhp=_map[nx][ny]==4?6:lhp-1;
            if(ok(nx,ny)&&nhp>0){
                hp.push(nhp);
                que.push(node(nx,ny));
                ans[nx][ny]=ans[lx][ly]+1;
            }
        }
    }
}
int main(int argc,const char *argv[]){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&_map[i][j]);
            ans[i][j]=-1;
            if(_map[i][j]==2){
                sx=i;
                sy=j;
            }
            if(_map[i][j]==3){
                ex=i;
                ey=j;
            }
        }
    }
    bfs(sx,sy);
    printf("%d\n",ans[ex][ey]);
    return 0;
}
2022/4/3 13:09
加载中...