作者：沈大森
链接：https://ac.nowcoder.com/discuss/374726?type=101&order=0&pos=1&page=0
来源：牛客网

#include<stdio.h>
#include<string.h>

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int fire[32][32],n,m,qi,qj;
char a[32][32];

struct node{
    int ci,cj;
    int step;
}queue[1000];

void f(int step2){  //把着火的坐标以正方形的方式扩展
    int temp=step2;

    int t10=qi,t11=qj; //得到着火点*的坐标
    int t20=qi,t21=qj;
    
    for(int i=0;i<temp;i++){ //得到火会到达的最小坐标和最大坐标
           t10=t10-1;
           t11=t11-1;
           t20=t20+1;
           t21=t21+1;
    }
    if(t10<0)t10=0;
    if(t20>=n)t20=n-1;
    if(t11<0)t11=0;
    if(t21>=m)t10=m-1;
    
    //得到火会到达的最小坐标和最大坐标，相当于得到正方形的左上角和右下角，然后循环把正方形填充完整，正方形的面积就是着火的地点
    for(int i=t10;i<=t20;i++)
        for(int j=t11;j<=t21;j++){
            fire[i][j]=1;
   
}
int bfs(int q1,int q2){
    int head=0,rear=1,tr=0;
    queue[1].ci=q1;queue[1].cj=q2;queue[1].step=0;

    fire[qi][qj]=1;    
    while(head<rear){
        head++;
        int x = queue[head].ci;
        int y = queue[head].cj;
        if(head>1){
            if(queue[head].step>queue[head-1].step)    //前面的步数小于后面的步数才扩展着火点
                    f(queue[rear].step);
        }            
             for(int i = 0; i < 4; i++) {
                 int nowx = x + dx[i];
                int nowy = y + dy[i];
                
                if(a[nowx][nowy]=='E' && fire[nowx][nowy]==0){
                    rear++;
                   queue[rear].ci=nowx;
                   queue[rear].cj=nowy;
                   queue[rear].step=queue[head].step+1;
                   return queue[rear].step;
                }
                if(a[nowx][nowy]=='.' && fire[nowx][nowy]==0 && nowx<n && nowx>=0 && nowy<m && nowy>=0){
                    rear++;
                   queue[rear].ci=nowx;
                   queue[rear].cj=nowy;
                   queue[rear].step=queue[head].step+1;    
                    a[nowx][nowy]='#';
                printf("此时走到%d %d\n",nowx,nowy);   

                }
                if(a[nowx][nowy]=='#'){
                    continue;
                }                        
             }                                                                        
    }
    return -1;
}
int main(){
    int ans,t,k=0;
    int b[300];
    scanf("%d",&t);
    memset(fire, 0, sizeof(fire));
    memset(b, 0, sizeof(b));
    for(int i=0;i<t;i++){
        scanf("%d%d",&n,&m);
        for(int j=0;j<n;j++){
            scanf("%s",a[j]);    
        }
            for(int ii=0;ii<n;ii++)
                for(int jj=0;jj<m;jj++){
                    if(a[ii][jj]=='*'){                    
                        qi=ii;qj=jj;                            
                    }                                                            
                }        
                for(int ii=0;ii<n;ii++)
                for(int jj=0;jj<m;jj++){                                    
                    if(a[ii][jj]=='S'){                        
                        ans=bfs(ii,jj);                    
                        b[k]=ans;                                                                                                                       
                        k++;
                        memset(fire, 0, sizeof(fire));    
                    }                                        
                }        
    }
    for(int i=0;i<t;i++){        
        if(b[i]==-1){
            printf("T_T\n");
        }                        
        else{
            printf("%d\n",b[i]);    
        }    
    }            
            return 0;
}