Python3 解法, 执行用时: 88ms, 内存消耗: 4772K, 提交时间: 2022-11-24 18:01:43

class node:
    def __init__(self, x, y, t):
        self.x = x
        self.y = y
        self.time = t



def fun():
    q = []
    n, m = list(map(int, input().split()))
    vis = [[0 for mmm in range(35)] for mm in range(35)]
    f = [[0 for mmm in range(35)] for mm in range(35)]
    mp = [[]]
    si = 0  # S为人的坐标
    sj = 0
    hi = 0  # *为火灾的坐标
    hj = 0
    for i in range(1, n + 1):
        mp.append(" " + input())
        if mp[-1].find("S") != -1:
            si = i
            sj = mp[-1].find("S")
        if mp[-1].find("*") != -1:
            hi = i
            hj = mp[-1].find("*")
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            f[i][j] = max(abs(i - hi), abs(j - hj))
    vis[si][sj] = 1
    x=si
    y=sj
    stepx = [1, -1, 0, 0]
    stepy = [0, 0, 1, -1]
    q.append(node(x, y, 0))
    while q:
        temp = q[0]
        q = q[1:]
        if mp[temp.x][temp.y] == "E":
            return temp.time
        if temp.time == f[temp.x][temp.y]:
            continue
        for i in range(4):
            xx = temp.x + stepx[i]
            yy = temp.y + stepy[i]
            if (temp.time + 1) <= f[xx][yy] and xx <= n and x >= 1 and m >= yy >= 1 \
                    and not vis[xx][yy] and mp[xx][yy] != "#":
                q.append(node(xx, yy, temp.time + 1))
                vis[xx][yy] = 1
    return "T_T"
t=int(input())
for i in range(t):
    print(fun())

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 488K, 提交时间: 2020-06-09 09:59:01

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 30
using namespace std;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,x,y,u,v,X,Y,d[N+5][N+5];char s[N+5][N+5];
struct S {int t,x,y;I S(CI i=0,CI a=0,CI b=0):t(i),x(a),y(b){}}q[N*N+5];
I void BFS()
{
	RI i,H=1,T=0;S k,t;q[++T]=S(d[x][y]=1,x,y);W(H<=T) for(k=q[H++],i=0;i^4;++i)
	{
		if(t=S(k.t+1,k.x+dx[i],k.y+dy[i]),t.x<1||t.x>n||t.y<1||t.y>m) continue;
		if(s[t.x][t.y]=='E'&&max(abs(t.x-X),abs(t.y-Y))>=t.t-1) return (void)(d[u][v]=t.t);
		if(d[t.x][t.y]||s[t.x][t.y]=='#'||max(abs(t.x-X),abs(t.y-Y))<t.t) continue;
		q[++T]=t,d[t.x][t.y]=t.t;
	}
}
int main()
{
	RI Tt,T,i,j;for(scanf("%d",&Tt),T=1;T<=Tt;++T)
	{
		for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%s",s[i]+1);
		for(i=1;i<=n;++i) for(j=1;j<=m;++j) d[i][j]=0,
			s[i][j]=='S'&&(x=i,y=j),s[i][j]=='E'&&(u=i,v=j),s[i][j]=='*'&&(X=i,Y=j);
		BFS(),d[u][v]?printf("%d\n",d[u][v]-1):puts("T_T");
	}return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 5ms, 内存消耗: 412K, 提交时间: 2023-03-06 15:34:18

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
int const mod=1000000007;
int t,n,m;
char s[66][33][33];
int fx[8][2]={0,1,1,0,-1,0,0,-1, -1,-1,-1,1,1,-1,1,1};
int bfs(){
	int ans=0;
	while(1){
		ans++;
		int flag=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				s[ans][i][j]=s[ans-1][i][j];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[ans-1][i][j]=='S')
				for(int z=0;z<4;z++){
					int x=i+fx[z][0],y=j+fx[z][1];
					if(s[ans-1][x][y]=='E') return ans;
					if(s[ans][x][y]=='.') {
						s[ans][x][y]='S';flag=1;
					}
				}
			}
		}
		if(flag==0) return 0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[ans-1][i][j]=='*')
				for(int z=0;z<8;z++){
					int x=i+fx[z][0],y=j+fx[z][1];
					s[ans][x][y]='*';
				}
			}
		}
	}
	return 0;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>s[0][i]+1;
		}
		int k=bfs();
		if(k==0){
			cout<<"T_T"<<endl;
		}else{
			cout<<k<<endl; 
		}		
	}
	return 0;
}