题解 | #迷宫#

###强行BFS

见代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f
#define sc scanf
#define pf printf
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;

#define rep(i,l,r) for(int i=l;i<=r;i++)
#define rrep(i,l,r) for(int i=l;i>=r;i--)
const int N = 2e5+5;
const ll mod = 1e9+7;
const ll eqs = 1e-9;
vector <int> vi;
vector <ll> vll;
vector <pll> vpll;
map <string,ll> mpsl;
map <ll,ll> mpll;

////ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
/////////一川烟草 满城风絮 梅子黄时雨//////////

int t,n,m;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int dx1[8] = {0, -1, 0, 1, 1, 1, -1, -1};
int dy1[8] = {-1, 0, 1, 0, 1, -1, 1, -1};
char a[31][31];
int firetime[31][31];
int kidstime[31][31];

void fire(int fx,int fy)
{    
    firetime[fx][fy]=0;
    queue <pii> q;
    q.push({fx,fy});
    
    while(!q.empty())
    {
        pii s;
        s.first=q.front().first;
        s.second=q.front().second;
        q.pop();
            
        rep(i,0,7)
        {
            int x=s.first+dx1[i];
            int y=s.second+dy1[i];
            
            if(x<0||x>=n||y<0||y>=m)    //越界
                continue;
            
            if(firetime[x][y]!=-1)    //记过了
                continue;
            
            firetime[x][y]=firetime[s.first][s.second]+1;
            
            q.push({x,y});
        }
    }
    
}

int kids(int sx,int sy,int ex,int ey)
{
    kidstime[sx][sy]=0;
    queue <pii> q;
    q.push({sx,sy});
    
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        
        rep(i,0,3)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            
            if(xx<0||xx>=n||yy<0||yy>=m)
                continue;
            
            if(a[xx][yy]=='#'||a[xx][yy]=='*')
                continue;
            
            if(kidstime[xx][yy]!=-1)
                continue;
            
            kidstime[xx][yy]=kidstime[x][y]+1;
            
            if(xx==ex&&yy==ey&&kidstime[xx][yy]<=firetime[xx][yy])
                return kidstime[xx][yy];
            
            if(kidstime[xx][yy]<firetime[xx][yy])
                q.push({xx,yy});
        }
    }
    return -1;
}


int main()
{
    cin>>t;
    while(t--)
    {
        int sx,sy,fx,fy,ex,ey;
        cin>>n>>m;
        rep(i,0,n-1)
        {
            rep(j,0,m-1)
            {
                cin>>a[i][j];
                if(a[i][j]=='S')    //起点
                {
                    sx=i;
                    sy=j;
                }
                if(a[i][j]=='*')    //火源
                {
                    fx=i;
                    fy=j;
                }
                if(a[i][j]=='E')    //终点
                {
                    ex=i;
                    ey=j;
                }
            }
        }
        memset(firetime,-1,sizeof(firetime));
        memset(kidstime,-1,sizeof(kidstime));
        fire(fx,fy);    //先计算出每个点火苗烧到的时间
//////////////////////////////初始化//////////////////////////////////////
        //好戏开始
        
        int d=kids(sx,sy,ex,ey);    //bfs起来
        
        if(d==-1)
            cout<<"T_T"<<endl;
        else
            cout<<d<<endl;
    }
 	return 0;
}




//
//       ██████╗ ██╗   ██╗ ██████╗
//       ██╔══██╗██║   ██║██╔════╝
//       ██████╔╝██║   ██║██║  ███╗
//       ██╔══██╗██║   ██║██║   ██║
//       ██████╔╝╚██████╔╝╚██████╔╝
//       ╚═════╝  ╚═════╝  ╚═════╝
//