【题目】点击打开链接

【解题思路】bfs，结构体中存放当前位置x,y以及走了dis的时间，全局变量dis[][]代表在（i,j）这个点的炸弹剩余时间。如果这题直接用结构体来存放位置，走了dis的时间以及炸弹爆炸的时间的话，会MLE(雾)，这题还有一个迷之T++==。还可以预处理起点，终点，R点的最小距离，跑最短路也可以。

【AC代码】

#pragma comment(linker, "/STACK:102400000,102400000")
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=1e9;
char maze[605][605];
int dis[605][605]; //到达(i,j)炸弹的时间
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
struct node{
    int x,y,dis;
};//位置(x,y)以及走了距离dis的时间
int T,n,m,k;
bool check(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m&&maze[x][y]!='W') return true;
    else return false;
}
int main()
{
    scanf("%d",&T);
    T++;
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0; i<n; i++) scanf("%s",maze[i]);
        queue<node>qu;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                dis[i][j]=inf;
                if(maze[i][j]=='S')
                {
                    qu.push(node{i,j,0});
                    dis[i][j]=0;
                }
            }
        }
        int ans=inf;
        node now,nex;
        while(!qu.empty())
        {
            now=qu.front();
            qu.pop();
            if(dis[now.x][now.y]+1==k) continue;//炸弹在k时间后爆炸
            for(int i=0; i<4; i++)
            {
                int dx=now.x+dir[i][0];
                int dy=now.y+dir[i][1];
                if(check(dx,dy))
                {
                    if(maze[dx][dy]=='E') ans=min(ans,now.dis+1);
                    if(dis[dx][dy]>dis[now.x][now.y]+1)
                    {
                        dis[dx][dy]=dis[now.x][now.y]+1;
                        if(maze[dx][dy]=='R') dis[dx][dy]=0;
                        qu.push(node{dx,dy,now.dis+1});
                    }
                }
            }
        }
        if(ans==inf)
        {
            puts("Poor RunningPhoton!");
        }
        else
            printf("%d\n",ans);
    }
    return 0;
}