补题：2018ACM-ICPC北京网络赛题A-Saving Tang Monk II

刺骨的言语ヽ痛彻心扉 2022-05-10 04:56 168阅读 0赞

题目链接：  
[Saving Tang Monk II][]

题目大意：  
给你一个n\*m的图，你要从S走到T，每走一步都要花费1的时间，现在有的房间会有不同，’.'代表空房间，走入后不会发生什么，'B’代表有氧气瓶的房间，每走入一次就能得到一罐氧气瓶（但持续呆在里面不会得到，氧气瓶的携带上限是5个），‘P’代表有加速药丸的房间，每走入一次都代表可以减少1的时间（携带无上限，其实可以直接认为是走进这个房间不消耗时间，题目就是为了迷惑人写这么多），’\#'代表有毒气的房间，每走入一次需要一罐氧气瓶，并且在其中还有呆一的时间(即走入要消耗1个氧气瓶，消耗2的时间)，问这从S走到T的最少花费时间，走不到输入-1。

解题思路：  
Emmm，比赛中用了BFS+三维vis去写，结果是过不了最后一个样例，因为发现第一次访问到T的不一定是最少时间访问。gg  
于是，试试最短路+分层图  
将图分成6层，即0-5个氧气瓶作为分的标准  
然后遇到\#就往下走一层，时间+2，遇到P就往上走一层，时间+0，其他就是在当前层图走，时间+1。  
代码实现即开3维的dis\[x\]\[y\]\[ox\],第三维代表氧气数，同样vis\[x\]\[y\]\[ox\]也是开三维  
然后用dijstra跑一遍最短路即可求出答案

AC代码：

#include <bits/stdc++.h>
    
    using namespace std;
    const int INF = 0x3f3f3f3f;
    char g[150][150];
    
    int dis[150][150][6],vis[150][150][6];
    
    int n,m;
    int dir[4][2] = {
       {1,0},{-1,0},{0,1},{0,-1}};
    
    struct node{
    	int x,y;
    	int ox,dis;
    	node(){}
    	node(int _x, int _y, int _ox, int d):x(_x),y(_y),ox(_ox),dis(d){}
    	bool operator<(const node &a)const{
    		return dis==a.dis? ox > a.ox : dis > a.dis;
    	}
    };
    
    void dijstra(int x,int y){
    	priority_queue<node> pq;
    	pq.push(node(x,y,0,0));
    	dis[x][y][0] = 0;
    	while(!pq.empty()){
    		node tmp = pq.top();
    		pq.pop();
    		if(vis[tmp.x][tmp.y][tmp.ox]) continue;
    		vis[tmp.x][tmp.y][tmp.ox] = 1;
    		for(int i=0; i<4; ++i){
    			int tx = tmp.x + dir[i][0];
    			int ty = tmp.y + dir[i][1];
    			if(tx < 0 || tx >=n || ty <0 || ty >=m) continue;
    			if(g[tx][ty]== '#'){
    				if(tmp.ox<=0) continue;
    				if(dis[tx][ty][tmp.ox-1] > tmp.dis+2){
    					dis[tx][ty][tmp.ox-1] = tmp.dis+2;
    					pq.push(node(tx,ty,tmp.ox-1,tmp.dis+2));
    				}
    			}
    			else if(g[tx][ty] == 'B'){
    				if(dis[tx][ty][tmp.ox+1] > tmp.dis+1){
    					dis[tx][ty][tmp.ox+1] = tmp.dis+1;
    					pq.push(node(tx,ty,tmp.ox+1,tmp.dis+1));
    				}
    			}
    			else if(g[tx][ty] == 'P'){
    				if(dis[tx][ty][tmp.ox] > tmp.dis){
    					dis[tx][ty][tmp.ox] = tmp.dis;
    					pq.push(node(tx,ty,tmp.ox,tmp.dis));
    				}
    			}else{ //S, T或 . 
    				if(dis[tx][ty][tmp.ox] > tmp.dis+1){
    					dis[tx][ty][tmp.ox] = tmp.dis+1;
    					pq.push(node(tx,ty,tmp.ox,tmp.dis+1));
    				}
    			}
    		}
    	}
    }
    
    int main(){
    	
    	while(~scanf("%d%d",&n,&m)&&n){
    		int sx,sy,ex,ey;
    		for(int i=0; i<n; ++i){
    			scanf("%s",g[i]);
    			for(int j=0; j<m; ++j){
    				if(g[i][j] == 'S') {
    					sx = i; sy =j;
    				}
    				if(g[i][j] == 'T'){
    					ex = i; ey = j;
    				}
    			}	
    		}
    		
    		memset(vis,0,sizeof(vis));
    		memset(dis,INF,sizeof(dis));
    		int ans = INF;
    		dijstra(sx,sy);
    		for(int i=0; i<=5; ++i){
    			ans = min(ans, dis[ex][ey][i]);
    		}
    		
    		if(ans==INF) cout<<"-1"<<endl;
    		else cout<<ans<<endl;
    	}
    	
    	return 0;
    }

[Saving Tang Monk II]: https://hihocoder.com/problemset/problem/1828