RunningPhoton's Nightmare

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 using namespace std;
  7 typedef pair<int,int> P;
  8 
  9 const int INF=100000000;
 10 
 11 char map[605][605];
 12 int N,M;
 13 int sx,sy;
 14 int gx,gy;
 15 
 16 int T,k,tot,cnt;
 17 int d[605][605],head[200],vis[200],dis[200],p[200][2];
 18 int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
 19 
 20 struct edge{
 21     int to,next;
 22     int w;
 23 }e[40000];
 24 
 25 void e_init(){
 26     tot=0;
 27     memset(head,-1,sizeof(head));
 28 }
 29 
 30 void addedge(int u,int v,int w){
 31     e[tot].to=v;
 32     e[tot].w=w;
 33     e[tot].next=head[u];
 34     head[u]=tot++;
 35 }
 36 
 37 void init(int np,int m_sx,int m_sy){
 38     queue<P> q;
 39     for(int i=0;i<N;i++){
 40         for(int j=0;j<M;j++)
 41             d[i][j]=INF;
 42     }
 43     q.push(P(m_sx,m_sy));
 44     d[m_sx][m_sy]=0;
 45     
 46     while(q.size()){
 47         P p=q.front();
 48         q.pop();
 49         for(int i=0;i<4;i++){
 50             int nx=p.first+dx[i],ny=p.second+dy[i];
 51             if(0<=nx&&nx<N&&0<=ny&&ny<M&&map[nx][ny]!='W'&&d[nx][ny]==INF){
 52                  q.push(P(nx,ny));
 53                  d[nx][ny]=d[p.first][p.second]+1;
 54             }
 55         }
 56     }
 57     for(int i=0;i<=cnt;i++){
 58         int mx=p[i][0],my=p[i][1];
 59         if(i==np||d[mx][my]>=k) continue;
 60         addedge(np,i,d[mx][my]);
 61     }
 62 }
 63 void SPFA(int st){
 64     for(int i=1;i<=cnt;i++){
 65         dis[i]=INF;
 66         vis[i]=0;
 67     }
 68     dis[st]=0;
 69     vis[st]=1;
 70     queue<int> q;
 71     q.push(st);
 72     while(q.size()){
 73         int v=q.front();
 74         q.pop();
 75         for(int i=head[v];i!=-1;i=e[i].next){
 76             int t=e[i].to;
 77             if(dis[t]>dis[v]+e[i].w){
 78                 dis[t]=dis[v]+e[i].w;
 79                 if(!vis[t]){
 80                     q.push(t);
 81                     vis[t]=1;
 82                 }
 83             }
 84         }
 85         vis[v]=0;
 86     }    
 87 }
 88 /*
 89 int BFS(int st,int en){
 90     queue<int> q;
 91     memset(dis,0,sizeof(dis));
 92     memset(vis,0,sizeof(vis));
 93     
 94     q.push(st);
 95     vis[st]=1;
 96     while(q.size()){
 97         int v=q.front();
 98         q.pop();
 99         for(int i=head[v];i!=-1;i=e[i].next){
100             int t=e[i].to;
101             if(!vis[t]){
102                 vis[t]=1;
103                 dis[t]=dis[v]+e[i].w;
104                 if(t==en) return dis[en];
105                 q.push(t);
106             }
107         }
108     }
109     return -1;
110 }
111 */
112 int main()
113 {   scanf("%d",&T);
114     while(T--){
115         cnt=0;
116         e_init();
117         scanf("%d%d%d",&N,&M,&k);
118         memset(p,0,sizeof(p));
119         for(int i=0;i<N;i++){
120             for(int j=0;j<M;j++){
121                 cin>>map[i][j];
122                 if(map[i][j]=='S') sx=i,sy=j;
123                 if(map[i][j]=='E') gx=i,gy=j;
124                 if(map[i][j]=='R'){
125                     cnt++;
126                     p[cnt][0]=i;
127                     p[cnt][1]=j;
128                 }
129             }
130             getchar(); 
131         }
132         cnt++;
133         p[0][0]=sx,p[0][1]=sy,p[cnt][0]=gx,p[cnt][1]=gy;
134         for(int i=0;i<=cnt;i++) 
135             init(i,p[i][0],p[i][1]);
136         SPFA(0);   
137         if(dis[cnt]==INF) printf("Poor RunningPhoton!\n");
138         else printf("%d\n",dis[cnt]);
139     }
140     return 0;
141 }