2018 北京赛区网络预选赛 A. Saving Tang Monk II

比眉伴天荒 2022-05-10 04:42 195阅读 0赞

## 题目：[点击打开链接][Link 1] ##

## 题意：S为起点，T为终点，.为空地，\#为毒气，B为氧气室，P为加速。每走一格时间花费1，入一个\#花费一个氧气瓶，无氧气不能入，入B能获得一个氧气，身上最多能携带5个氧气，入P不花费时间，求起点到终点的最小花费时间。 ##

## 分析：因为最多能带5个氧气，所以每次入毒都只有那几种可能，所以可将二维图扩展为三维的状态。每个地方相同的状态进入结果是相同的，所以标记的vis数组扩展为3维即可。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    int n,m,sx,sy,ex,ey;
    bool vis[102][102][6];
    char s[110][110];
    struct nd {
        int x,y,num,step;
        nd(int x,int y,int num,int step) : x(x), y(y), num(num), step(step) {}
        bool operator < (const nd &a) const {
            if(step==a.step) return a.num<num;
            return a.step<step;
        }
    };
    
    int bfs() {
        priority_queue<nd> q;
        memset(vis,0,sizeof(vis));
        vis[sx][sy][0]=1;
        q.push(nd(sx,sy,0,0));
        while(!q.empty()) {
            nd tp=q.top(); q.pop();
            if(tp.x==ex&&tp.y==ey) return tp.step;
            for(int i=0;i<4;i++) {
                int xx=tp.x+to[i][0],yy=tp.y+to[i][1],now=tp.num;
                if( 1<=xx&&xx<=n && 1<=yy&&yy<=m ) {
                    if( (s[xx][yy]=='.' || s[xx][yy]=='S' || s[xx][yy]=='T') &&  !vis[xx][yy][now]  )
                        vis[xx][yy][now]=1,
                        q.push(nd(xx,yy,now,tp.step+1));
                    if( now<5 && s[xx][yy]=='B' && !vis[xx][yy][now+1] )///大于等于5个就不需要再去了
                        vis[xx][yy][now+1]=1,
                        q.push(nd(xx,yy,now+1,tp.step+1));
                    if( s[xx][yy]=='P' && !vis[xx][yy][now] )
                        vis[xx][yy][now]=1,
                        q.push(nd(xx,yy,now,tp.step));
                    if( now>0 && s[xx][yy]=='#' && !vis[xx][yy][now-1] )
                        vis[xx][yy][now-1]=1,
                        q.push(nd(xx,yy,now-1,tp.step+2));
                }
            }
        }
        return -1;
    }
    
    int main() {
        while(scanf("%d%d",&n,&m)!=EOF) {
            if(n+m==0) break;
            for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    if(s[i][j]=='S') sx=i,sy=j;
                    else if(s[i][j]=='T') ex=i,ey=j;
            printf("%d\n",bfs());
        }
        return 0;
    }

[Link 1]: https://hihocoder.com/problemset/problem/1828