poj 3083 -- Children of the Candy Corn

  1 /*======================================================================
  2  *           Author :   kevin
  3  *         Filename :   ChildrwenOftheCandyCorn.cpp
  4  *       Creat time :   2014-06-08 15:37
  5  *      Description :
  6 ========================================================================*/
  7 #include <iostream>
  8 #include <algorithm>
  9 #include <cstdio>
 10 #include <cstring>
 11 #include <queue>
 12 #include <cmath>
 13 #define clr(a,b) memset(a,b,sizeof(a))
 14 #define M 50
 15 using namespace std;
 16 char grap[M][M];
 17 int w,h,sx,sy,ex,ey;
 18 int vis[M][M],cntl,cntr;
 19 int minsteps[M][M];
 20 int dir0[4][2]={{0,-1},{-1,0},{0,1},{1,0}};//dfs needed
 21 int dir[4][4][2] = {//bfs needed
 22                 {{0,-1},{-1,0},{0,1},{1,0}},
 23                 {{-1,0},{0,1},{1,0},{0,-1}},
 24                 {{0,1},{1,0},{0,-1},{-1,0}},
 25                 {{1,0},{0,-1},{-1,0},{0,1}}
 26 };
 27 struct Node
 28 {
 29     int x,y;
 30 };
 31 void BFS()
 32 {
 33     queue<Node>que;
 34     Node node;
 35     node.x = sx; node.y = sy;
 36     que.push(node);
 37     vis[sx][sy] = 1;
 38     minsteps[sx][sy] = 1;
 39     int flag = 0;
 40     while(que.empty() != true){
 41         Node T = que.front();
 42         que.pop();
 43         if(T.x == ex && T.y == ey) return ;
 44         for(int i = 0; i < 4; i++){
 45             int x = T.x + dir[1][i][0];
 46             int y = T.y + dir[1][i][1];
 47             if(grap[x][y] == ‘.‘ && !vis[x][y]){
 48                 node.x = x; node.y = y;
 49                 vis[x][y] = 1;
 50                 que.push(node);
 51                 minsteps[x][y] = minsteps[T.x][T.y]+1;
 52             }
 53             else if(grap[x][y] == ‘E‘){
 54                 minsteps[x][y] = minsteps[T.x][T.y]+1;
 55                 flag = 1; break;
 56             }
 57         }
 58         if(flag) break;
 59     }
 60 }
 61 int lDFS(int i,int j,int s,int now)
 62 {
 63     if(grap[i][j]==‘E‘)return s;
 64     for(int d=now;d<now+4;++d)
 65     {
 66         int di=i+dir0[d%4][0];
 67         int dj=j+dir0[d%4][1];
 68         if(d<=0)d+=4;
 69         if(grap[di][dj]!=‘#‘)return lDFS(di,dj,s+1,(d-1)%4);
 70         d%=4;
 71     }
 72     return -1;
 73 }
 74 int rDFS(int i,int j,int s,int now)
 75 {
 76     if(grap[i][j]==‘E‘)return s;
 77     for(int d=now+4;d>now;--d)
 78     {
 79         int di=i+dir0[d%4][0];
 80         int dj=j+dir0[d%4][1];
 81         if(grap[di][dj]!=‘#‘)return rDFS(di,dj,s+1,(d+1)%4);
 82     }
 83     return -1;
 84 }
 85 int main(int argc,char *argv[])
 86 {
 87     int cas;
 88     scanf("%d",&cas);
 89     while(cas--){
 90         scanf("%d%d",&w,&h);
 91         clr(vis,0);
 92         memset(grap,‘#‘,sizeof(grap));
 93         clr(minsteps,0);
 94         for(int i = 1; i <= h; i++){
 95             getchar();
 96             for(int j = 1; j <= w; j++){
 97                 scanf("%c",&grap[i][j]);
 98                 if(grap[i][j] == ‘S‘){
 99                     sx = i; sy = j;
100                 }
101                 if(grap[i][j] == ‘E‘){
102                     ex = i; ey = j;
103                 }
104             }
105         }
106         printf("%d %d ",lDFS(sx,sy,1,0),rDFS(sx,sy,1,0));
107         BFS();
108         printf("%d\n",minsteps[ex][ey]);
109     }
110     return 0;
111 }