题解 | #A-逃脱#

//两次BFS（通俗易懂）

#include<bits/stdc++.h>
using namespace std;
char g[35][35];
int mx,my,n,m,nx,ny;
int dis1[35][35],dis2[35][35];
int dx1[]={-1,-1,-1,0,0,1,1,1};
int dy1[]={-1,0,1,-1,1,-1,0,1};
int dx2[]={-1,1,0,0};
int dy2[]={0,0,-1,1};
int main(){
    int t;cin>>t;
    while(t--){
        cin>>n>>m;
        //初始化
        memset(dis1,0x3f, sizeof(dis1));
        memset(dis2,0x3f, sizeof(dis2));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                char c;cin>>c;
                g[i][j]=c;
                if(c=='S')    mx=i,my=j;
                if(c=='*')    nx=i,ny=j;
            }
        queue<pair<int,int>> p,q;
        dis1[nx][ny]=0;//火蔓延到nx,ny的时间为第0时刻
        dis2[mx][my]=0;//角色到达位置mx,my的时间为第0时刻
        p.push({nx,ny});
        while(!p.empty()){
            int x=p.front().first;
            int y=p.front().second;
            p.pop();
            for(int i=0;i<8;i++){
                int xx=x+dx1[i],yy=y+dy1[i];
                if(xx<0||yy<0||xx>=n||yy>=m)    continue;
                //不用考虑墙，因为直接可以被烧掉
                if(dis1[xx][yy]<=dis1[x][y]+1)    continue;
                //到达xx,yy位置的时刻为前一个位置x,y的时刻的基础上+1
                dis1[xx][yy]=dis1[x][y]+1;
                p.push({xx,yy});
            }
        }
        q.push({mx,my});
        g[mx][my]=='#';
        int flag=0;
        while(!q.empty()){
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            for(int i=0;i<8;i++){
                int xx=x+dx2[i],yy=y+dy2[i];
                if(xx<0||yy<0||xx>=n||yy>=m)    continue;
                //如果为墙，那么角色无法通过
                if(g[xx][yy]=='#')    continue;
                if(dis2[xx][yy]<=dis2[x][y]+1)    continue;
                //注意是先角色移动，然后火移动
                //1.如果角色移动到一个位置之后，火不会移动到那个位置，那么角色安全否则不安全
                if(dis2[x][y]+1<dis1[xx][yy]){
                    q.push({xx,yy});
                    dis2[xx][yy]=dis2[x][y]+1;
                    if(g[xx][yy]=='E'){
                        flag=1;
                        cout<<dis2[xx][yy]<<endl;
                        break;
                    }
                }
                //2.如果角色移动到一个位置之后，火也来了，但是如果那个位置正好是出口，那么
                //角色就可以在火移动之前就逃离，输出答案，结束循环
                else if(dis2[x][y]+1==dis1[xx][yy]&&g[xx][yy]=='E'){
                    flag=1;
                    dis2[xx][yy]=dis2[x][y]+1;
                    cout<<dis2[xx][yy]<<endl;
                    break;
                }
                //其他情况就是角色到达某一个位置之前，那个位置就已经起火了，不安全
                //把已经移动到的位置标记为墙，那么之后就不用继续访问这一个位置
                g[xx][yy]=='#';
            }
            if(flag)    break;
        }
        if(!flag)    cout<<"T_T"<<endl;
    }
    return 0;
}