ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 A（bfs）

传送门

题面：

#1828 : Saving Tang Monk II

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng'en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.

During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.

Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace, and he wanted to reach Tang Monk and rescue him.

The palace can be described as a matrix of characters. Different characters stand for different rooms as below:

'S' : The original position of Sun Wukong

'T' : The location of Tang Monk

'.' : An empty room

'#' : A deadly gas room.

'B' : A room with unlimited number of oxygen bottles. Every time Sun Wukong entered a 'B' room from other rooms, he would get an oxygen bottle. But staying there would not get Sun Wukong more oxygen bottles. Sun Wukong could carry at most 5 oxygen bottles at the same time.

'P' : A room with unlimited number of speed-up pills. Every time Sun Wukong entered a 'P' room from other rooms, he would get a speed-up pill. But staying there would not get Sun Wukong more speed-up pills. Sun Wukong could bring unlimited number of speed-up pills with him.

Sun Wukong could move in the palace. For each move, Sun Wukong might go to the adjacent rooms in 4 directions(north, west,south and east). But Sun Wukong couldn't get into a '#' room(deadly gas room) without an oxygen bottle. Entering a '#' room each time would cost Sun Wukong one oxygen bottle.

Each move took Sun Wukong one minute. But if Sun Wukong ate a speed-up pill, he could make next move without spending any time. In other words, each speed-up pill could save Sun Wukong one minute. And if Sun Wukong went into a '#' room, he had to stay there for one extra minute to recover his health.

Since Sun Wukong was an impatient monkey, he wanted to save Tang Monk as soon as possible. Please figure out the minimum time Sun Wukong needed to reach Tang Monk.

输入

There are no more than 25 test cases.

For each case, the first line includes two integers N and M(0 < N,M ≤ 100), meaning that the palace is a N × M matrix.

Then the N×M matrix follows.

The input ends with N = 0 and M = 0.

输出

For each test case, print the minimum time (in minute) Sun Wukong needed to save Tang Monk. If it's impossible for Sun Wukong to complete the mission, print -1

样例输入

2 2
S#
#T
2 5
SB###
##P#T
4 7
SP.....
P#.....
......#
B...##T
0 0

样例输出

-1
8
11

题意：

    你要从S走到T，其中每经过一次B，你将获得一罐氧气，你最多可以获得5罐氧气；每经过一次P，你可以获得一个加速器（你可以拥有无限多个加速器）。拥有一个加速器可以使得某一时刻走到下一个时刻不需要时间。每经过一次#，你需要花费一罐氧气，且需要花费额外的1单位时间，你没有氧气无法进入#。现在问你从S到T的最短路径。

题目分析：

    题目中是要求我们求从S到T的最短路径，因此我们不难想到可以用bfs进行解决。而在这个题中，最难处理的一点就是氧气瓶数量。

    为了解决氧气瓶的问题，因此我们可以在常规的dis数组的基础上再开一维状态用来记录现在拿了多少瓶氧气瓶，即代表着现在位于点处，拥有num个氧气瓶。

    而因为在之后的更新中，因为P的存在，导致了某些状态可以能会重复遍历，因此我们不能采用vis数组判重的方法去重，我们需要采用类似最短路松弛操作的做法，当发现一条更短的路径时才更新当前的状态。

代码：

#include <bits/stdc++.h>
#define maxn 105
using namespace std;
const int INF=0x3f3f3f3f;
struct Node{int x,y,num;Node(int _x,int _y,int _num){x=_x,y=_y,num=_num;}
};
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int dis[maxn][maxn][10];
char str[maxn][maxn];
int n,m;
int sx,sy,tx,ty;
void bfs(int x,int y){memset(dis,INF,sizeof(dis));queue<Node> que;dis[x][y][0]=0;que.push(Node(x,y,0));while(!que.empty()){Node now=que.front();que.pop();for(int i=0;i<4;i++){Node to=Node(0,0,0);to.x=now.x+dir[i][0];to.y=now.y+dir[i][1];if((to.x>=n||to.x<0)||(to.y>=m||to.y<0)) continue;if(str[to.x][to.y]=='B'&&now.num<5) to.num=now.num+1;//当前处于氧气状态，且之前的氧气瓶数量少于u，则获取else to.num=now.num;// 否则直接覆盖int tmp=INF;//用tmp作为松弛的条件if(str[to.x][to.y]!='#') tmp=dis[now.x][now.y][now.num]+1;//不是毒气，则直接+1else if(to.num>=1){//为#且氧气数量大于1to.num--;tmp=dis[now.x][now.y][now.num]+2;}if(str[to.x][to.y]=='P') tmp--;if(dis[to.x][to.y][to.num]>tmp){//松弛操作dis[to.x][to.y][to.num]=tmp;que.push(to);}}}
}
int main()
{while(~scanf("%d%d",&n,&m)){if(n==0&&m==0) break;for(int i=0;i<n;i++) scanf("%s",str[i]);for(int i=0;i<n;i++){for(int j=0;j<m;j++)if(str[i][j]=='S') sx=i,sy=j;else if(str[i][j]=='T') tx=i,ty=j;}bfs(sx,sy);int ans=0x3f3f3f3f;for(int i=0;i<=5;i++) ans=min(ans,dis[tx][ty][i]);if(ans>=INF) printf("-1\n");else printf("%d\n",ans);}return 0;
}