1 #include<cstdio>  2 #include<cstring>  3 #include<queue>  4 #define mt(a,b) memset(a,b,sizeof(a))  5 using namespace std;  6 const int inf=0x3f3f3f3f;  7 const int M=1024;  8 int t,n,m;  9 char a[M][M]; 10 int d[M][M]; 11 int dx[]={0,0,1,-1}; 12 int dy[]={1,-1,0,0}; 13 struct Q{ 14     int x,y,step; 15 }now,pre; 16 queue<Q> q; 17 bool inside(const int &x,const int &y){ 18     if(x>=0&&x<n&&y>=0&&y<m) return true; return false; 19 } 20 void bfs(){ 21     for(int i=0;i<n;i++){ 22         for(int j=0;j<m;j++){ 23             d[i][j]=inf; 24         } 25     } 26     while(!q.empty()) q.pop(); 27     for(int i=0;i<n;i++){ 28         for(int j=0;j<m;j++){ 29             if(a[i][j]==‘F‘){ 30                 now.x=i; 31                 now.y=j; 32                 now.step=0; 33                 d[i][j]=0; 34                 q.push(now); 35             } 36         } 37     } 38     while(!q.empty()){ 39         pre=q.front(); 40         q.pop(); 41         for(int i=0;i<4;i++){ 42             int tx=pre.x+dx[i]; 43             int ty=pre.y+dy[i]; 44             if(!inside(tx,ty)||a[tx][ty]==‘#‘) continue; 45             now.step=pre.step+1; 46             if(d[tx][ty]>now.step){ 47                 d[tx][ty]=now.step; 48                 now.x=tx; 49                 now.y=ty; 50                 q.push(now); 51             } 52         } 53     } 54 } 55 bool out(const Q &a){ 56     if(a.x==0||a.x==n-1||a.y==0||a.y==m-1) return true; return false; 57 } 58 bool vis[M][M]; 59 int solve(){ 60     mt(vis,0); 61     while(!q.empty()) q.pop(); 62     for(int i=0;i<n;i++){ 63         for(int j=0;j<m;j++){ 64             if(a[i][j]==‘J‘){ 65                 vis[i][j]=true; 66                 now.x=i; 67                 now.y=j; 68                 now.step=0; 69                 q.push(now); 70             } 71         } 72     } 73     while(!q.empty()){ 74         pre=q.front(); 75         q.pop(); 76         if(out(pre)) return pre.step+1; 77         for(int i=0;i<4;i++){ 78             int tx=pre.x+dx[i]; 79             int ty=pre.y+dy[i]; 80             if(!inside(tx,ty)||a[tx][ty]==‘#‘||vis[tx][ty]||d[tx][ty]<=pre.step+1) continue; 81             vis[tx][ty]=true; 82             now.x=tx; 83             now.y=ty; 84             now.step=pre.step+1; 85             q.push(now); 86         } 87     } 88     return -1; 89 } 90 int main(){ 91     while(~scanf("%d",&t)){ 92         while(t--){ 93             scanf("%d%d",&n,&m); 94             for(int i=0;i<n;i++){ 95                 scanf("%s",a[i]); 96             } 97             bfs(); 98             int ans=solve(); 99             if(~ans) printf("%d\n",ans);100             else puts("IMPOSSIBLE");101         }102     }103     return 0;104 }

  1 #include<cstdio>  2 #include<algorithm>  3 #include<queue>  4 using namespace std;  5 const int inf=0x3f3f3f3f;  6 const int M=32;  7 int n,m;  8 char a[M][M];  9 int dp[M][M][8][4]; 10 struct Q{ 11     int x,y,step,color,dir; 12 }now,pre; 13 queue<Q> q; 14 int dx[]={-1,0,1,0}; 15 int dy[]={0,1,0,-1}; 16 Q turnright(const Q &pre){ 17     Q now; 18     now.color=pre.color; 19     now.x=pre.x; 20     now.y=pre.y; 21     now.dir=(pre.dir+1)%4; 22     now.step=pre.step+1; 23     return now; 24 } 25 Q turnleft(const Q &pre){ 26     Q now; 27     now.color=pre.color; 28     now.x=pre.x; 29     now.y=pre.y; 30     now.dir=pre.dir-1; 31     if(now.dir==-1) now.dir=3; 32     now.step=pre.step+1; 33     return now; 34 } 35 Q ahead(const Q &pre){ 36     Q now; 37     now.color=(pre.color+1)%5; 38     now.x=pre.x+dx[pre.dir]; 39     now.y=pre.y+dy[pre.dir]; 40     now.dir=pre.dir; 41     now.step=pre.step+1; 42     return now; 43 } 44 bool inside(const Q &now){ 45     if(now.x>=0&&now.x<n&&now.y>=0&&now.y<m) return true; return false; 46 } 47 void go(const Q &now){ 48     if(!inside(now)||a[now.x][now.y]==‘#‘) return ; 49     if(dp[now.x][now.y][now.color][now.dir]>now.step){ 50         dp[now.x][now.y][now.color][now.dir]=now.step; 51         q.push(now); 52     } 53 } 54 void bfs(){ 55     for(int i=0;i<n;i++){ 56         for(int j=0;j<m;j++){ 57             for(int k=0;k<5;k++){ 58                 for(int u=0;u<4;u++){ 59                     dp[i][j][k][u]=inf; 60                 } 61             } 62         } 63     } 64     for(int i=0;i<n;i++){ 65         for(int j=0;j<m;j++){ 66             if(a[i][j]==‘S‘){ 67                 now.x=i; 68                 now.y=j; 69             } 70         } 71     } 72     dp[now.x][now.y][0][0]=0; 73     now.color=0; 74     now.dir=0; 75     now.step=0; 76     while(!q.empty()) q.pop(); 77     q.push(now); 78     while(!q.empty()){ 79         pre=q.front(); 80         q.pop(); 81         now=turnright(pre); 82         go(now); 83         now=turnleft(pre); 84         go(now); 85         now=ahead(pre); 86         go(now); 87     } 88 } 89 int main(){ 90     int cas=1; 91     while(~scanf("%d%d",&n,&m),n|m){ 92         for(int i=0;i<n;i++){ 93             scanf("%s",a[i]); 94         } 95         bfs(); 96         int ex,ey; 97         for(int i=0;i<n;i++){ 98             for(int j=0;j<m;j++){ 99                 if(a[i][j]==‘T‘){100                     ex=i;101                     ey=j;102                 }103             }104         }105         if(cas>1) puts("");106         printf("Case #%d\n",cas++);107         int ans=inf;108         for(int i=0;i<4;i++){109             ans=min(ans,dp[ex][ey][0][i]);110         }111         if(ans<inf){112             printf("minimum time = %d sec\n",ans);113         }114         else{115             puts("destination not reachable");116         }117     }118     return 0;119 }