题解 | #A-逃脱#

用数组维护可以走的方向和火移动的方向。

BFS: 可以将‘S’所在的地方扩散出去，如果是'#''F''S'就不能扩散，反之则可以，用队列维护边缘坐标。

记住：当边缘坐标被火吞没时，该坐标不能移动，这需要特别判定。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

#define MAXSIZE 50
char mat[MAXSIZE][MAXSIZE];
queue<pair<int,int>>fire;
queue<pair<int,int>>per;
int udlr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int sur[8][2]={{1,0},{-1,0},{0,1},{0,-1},
                {1,1},{-1,-1},{1,-1},{-1,1}};
bool run(pair<int,int> pos){
    if(mat[pos.first][pos.second]=='*'){
        return false;
    }
    for(int i=0;i<4;++i){
        char* temp=&mat[pos.first+udlr[i][0]][pos.second+udlr[i][1]];
        switch (*temp)
        {
        case '.':
            *temp='S';
            per.push({pos.first+udlr[i][0],pos.second+udlr[i][1]});
            break;
        case 'E':
            return true;
        }
    }
    return false;
}
bool isEndAndSpread(pair<int,int>pos){
    for(int i=0;i<8;++i){
        char* temp=&mat[pos.first+sur[i][0]][pos.second+sur[i][1]];
        switch (*temp)
        {
        case '.':
        case '#':
        case 'S':
            *temp='*';
            fire.push({pos.first+sur[i][0],pos.second+sur[i][1]});
            break;
        case 'E':
            return true;
        }
    }
    return false;
}
void initializeEdge(int n,int m){
    for(int i=0;i<=n+1;++i){
        mat[i][0]=mat[i][m+1]='*';
    }
    for(int i=0;i<=m+1;++i){
        mat[0][i]=mat[n+1][i]='*';
    }
}
int gettime(){
    int time=1;
    while(!per.empty()){//people can go somewhere
        int persize=per.size();
        while(persize--){
            if(run(per.front())){
                return time;
            }else{
                per.pop();
            }
        }
        int firesize=fire.size();
        while(firesize--){
            if(isEndAndSpread(fire.front())){
                return -1;
            }else{
                fire.pop();
            }
        }
        ++time;
    }
    return -1;
}

int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
    int T;
    cin>>T;
    while(T--){
        while(!fire.empty())fire.pop();
        while(!per.empty())per.pop();
        int n,m;
        cin>>n>>m;
        initializeEdge(n,m);
        cin.get();
        for(int in=1;in<=n;++in){
            for(int im=1;im<=m;++im){
                mat[in][im]=cin.get();
                if(mat[in][im]=='S'){
                    per.push({in,im});
                }else if(mat[in][im]=='*'){
                    fire.push({in,im});
                }
            }
            cin.get();
        }
        int time=gettime();
        if(time==-1){
            cout<<"T_T"<<endl;
        }else{
            cout<<time<<endl;
        }
    }
}