转载：
https://blog.csdn.net/qq_41668093/article/details/82845044

题意

给一个100x100的迷宫，’.'表示路面，'S’表示起点，‘T’表示终点；’#'表示毒气区，进入毒气区必须要消耗一个氧气；'B’表示氧气区，每次进入自动获得一个氧气，可反复进入从而获得多个，但最多携带5个；'P’表示加速药，获得原理和氧气一样，使用后使下一次移动不耗时，可以无限携带。一次移动可以移动到相邻的四个格子，花费一个单位时间，如果移动到了毒气区，将在毒气区额外停留一个单位时间。求从S到T的最短时间，如果不能到达，输出-1。

分析

氧气数量是这道题的关键，所以把状态定义为(x, y, n)，表示在(x,y)时还有n个氧气，当氧气<=0，就不能向毒气区转移了；同时我们还希望求出的最短时间，所以dp[x][y][n]=t，表示从起点出发到达状态(x, y, n)花费的最少时间，这样以后，如果终点是(tx,ty)，那么只要dp[tx][ty][i],(i=0,1,2,3,4,5)中任何一个不是无穷大，就是可以到达终点的。
接下来是状态之间的转移：
(x, y, n)可以向四个方向转移，假设下一个地方是(tx,ty)，那么：
(tx,ty)是’.‘或’S’，就用dp[x][y][n]+1更新dp[tx][ty][n]；
(tx,ty)是’T’，同样用dp[x][y][n]+1更新dp[tx][ty][n]，并且不再向下转移；
(tx,ty)是’B’，氧气数量增加，如果n<5，那么还可以拿氧气，用dp[x][y][n]+1更新dp[tx][ty][n+1]，否则更新dp[tx][ty][n]；
(tx,ty)是’P’，下一步不耗时，用dp[x][y][n]更新dp[tx][ty][n]；
(tx,ty)是’#’，氧气数量减少，只有当n>0时，才可以进毒气区，因为要额外花费一个单位时间，用dp[x][y][n]+2更新dp[tx][ty][n-1]。
那么所有的转移都搞定了，初始状态很简单，假设起点是(sx,sy)，那么就是dp[sx][sy][0]=0，其他所有的状态都是INF。只要把所有可能到达的状态更新了，那么答案就在dp[tx][ty][i]中取最小就行了。
需要注意的是，状态的更新需要用类似于BFS的顺序，不断的用已知的最优状态，去更新相邻的未知状态，直至遍历完所有的状态，复杂度为O(5nm)。

//也就是普通的二维BFS多加了一个 氧气瓶 B 的变量与 毒气的关系
#include<bits/stdc++.h>
using namespace std;
const int  N=105;
const int M=0x3f3f3f3f;
int dp[N][N][8];
char mp[N][N];
int d[2][4]= {0,1,0,-1,1,0,-1,0};
struct node
{
  int x,y,n;//位置 x y 氧气瓶数 n
};
int main()
{
  int i,j,n,m,t;
  int sx,sy,ex,ey;//起点 终点
  while(~scanf("%d %d",&n,&m))
  {
    if(!n&&!m) break;
    for(int i=1; i<=n; i++)
    {
      scanf("%s",mp[i]+1);
      for(int j=1; j<=m; j++)
      {
        if(mp[i][j]=='S') sx=i,sy=j;
        else if(mp[i][j]=='T') ex=i,ey=j;
        for(int k=0; k<=5; k++) dp[i][j][k]=M;//初始化
      }
    }
    queue<node>q;
    dp[sx][sy][0]=0;
    q.push(node{sx,sy,0});
    while(!q.empty())//BFS
    {
      node t=q.front();
      q.pop();
 
      for(int i=0; i<4; i++)//四个方向
      {
        int x=t.x+d[1][i];
        int y=t.y+d[0][i];
        int c=t.n;
        if(x>n||y>m||x<1||y<1) continue;//出界
        switch(mp[x][y])
        {
 
        case 'S'://起点
        case '.'://空地
          if(dp[x][y][c]>dp[t.x][t.y][c]+1)//秒数比较
          {
            dp[x][y][c]=dp[t.x][t.y][c]+1;
            q.push(node{x,y,c});
          }
          break;
        case 'T'://终点
          if(dp[x][y][c]>dp[t.x][t.y][c]+1)//秒数比较
          {
            dp[x][y][c]=dp[t.x][t.y][c]+1;
            q.push(node{x,y,c});
          }
          break;
        case '#'://毒气
          if(c>0&&dp[x][y][c-1]>dp[t.x][t.y][c]+2)//氧气瓶数>0 氧气瓶-1 花费秒数+2
          {
            dp[x][y][c-1]=dp[t.x][t.y][c]+2;
            q.push(node{x,y,c-1});
          }
          break;
        case 'B'://氧气
          if(c<5&&dp[x][y][c+1]>dp[t.x][t.y][c]+1)//氧气瓶+1 秒数+1
          {
            dp[x][y][c+1]=dp[t.x][t.y][c]+1;
            q.push(node{x,y,c+1});
          }
          else if(c==5&&dp[x][y][c]>dp[t.x][t.y][c]+1)//不拿氧气瓶 比较秒数
          {
            dp[x][y][c]=dp[t.x][t.y][c]+1;
            q.push(node{x,y,c});
          }
          break;
        case 'P'://加速
          if(dp[x][y][c]>dp[t.x][t.y][c]) //加速 不用花费秒数
          {
            dp[x][y][c]=dp[t.x][t.y][c];
            q.push(node{x,y,c});
          }
          break;
        default://其他
          break ;
 
        }
      }
    }
    int ans=M;
    for(int k=0; k<=5; k++)//寻找终点最小值
      ans=min(ans,dp[ex][ey][k]);
    
    if(ans>=M) printf("-1\n");//到达不了
    else printf("%d\n",ans);
  }
}