POJ 3083 Children of the Candy Corn dfs+bfs

题目大意：一看就是基本的迷宫问题，一个是优先往左走，一个优先往右走，还有一个是求最短。

额。。。。好久没写bfs= =...上来bfs没加vis= =。。。。然后dfs又写错，因为是左右思路相同，我是直接复制的，找了好久一直是re= =、你妹妹的。。。

用一个全局变量保存朝向，用一个%4来保存结果

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 char map[100][100];
  4 int m,n,sx,sy,dx,dy;
  5 int dir;
  6 int lx[4] = {1,0,-1,0};
  7 int ly[4] = {0,-1,0,1};
  8 int rx[4] = {-1,0,1,0};
  9 int ry[4] = {0,-1,0,1};
 10 int leap = 0;
 11 struct node
 12 {
 13     int x,y,step;
 14 }q[100000];
 15 int is_map(int x,int y)
 16 {
 17     if(x >= 0 &&x < n && y >= 0 && y < m)
 18     return 1;
 19     return 0;
 20 }
 21 
 22 int dfs(int is_left,int x,int y,int step)
 23 {
 24     if(is_map(x,y) == 0)
 25     return 0;
 26     if(map[x][y] == '#')
 27     return 0;
 28     if(map[x][y] == 'E')
 29     return step+1;
 30 
 31     if(is_left)
 32     {
 33         dir = (dir+3)%4;
 34         while(1)
 35         {
 36             int tx,ty;
 37             tx = x+lx[dir];
 38             ty = y+ly[dir];
 39             leap = dfs(1,tx,ty,step+1);
 40             if(leap)
 41             break;
 42             dir = (dir+1)%4;
 43         }
 44     }
 45     else
 46     {
 47         dir = (dir+3)%4;
 48         while(1)
 49         {
 50             int tx,ty;
 51             tx = x+rx[dir];
 52             ty = y+ry[dir];
 53             leap = dfs(0,tx,ty,step+1);
 54             if(leap > 0)
 55             break;
 56             dir = (dir+1)%4;
 57         }
 58     }
 59     return leap;
 60 }
 61 void bfs()
 62 {
 63     int vis[45][45] = {0};
 64     int f,r,i;
 65     f = r = 0;
 66     q[f].x = sx;
 67     q[r].y = sy;
 68     q[r].step = 1;
 69     r++;
 70     while(f<r)
 71     {
 72         struct node temp;
 73         temp = q[f++];
 74         for(i = 0;i < 4;i++)
 75         {
 76             struct node now;
 77             now.x = temp.x+lx[i];
 78             now.y = temp.y+ly[i];
 79             now.step = temp.step+1;
 80             if(is_map(now.x,now.y) && !vis[now.x][now.y])
 81             {
 82                 if(map[now.x][now.y] == 'E')
 83                 {
 84                     printf("%d\n",now.step);
 85                     return;
 86                 }
 87                 vis[now.x][now.y] = 1;
 88                 if(map[now.x][now.y] != '#')
 89                 q[r++] = now;
 90             }
 91         }
 92     }
 93 
 94 }
 95 int main()
 96 {
 97     int i,j,t,lsum,rsum;
 98     leap = 0;
 99     scanf("%d",&t);
100     while(t--){
101 
102     scanf("%d %d",&m,&n);
103         for(i = 0;i < n;i++)
104         {
105             scanf("%s",map[i]);
106 
107         }
108         for(i = 0;i < n;i++)
109         for(j = 0;j < m;j++)
110             {
111                 if(map[i][j] == 'S')
112                 sx = i,sy = j;
113                 if(map[i][j] == 'E')
114                 dx = i,dy = j;
115             }
116 
117 
118         dir = 0;
119         leap = 0;
120         lsum = dfs(1,sx,sy,0);
121         dir = 0;
122         rsum = dfs(0,sx,sy,0);
123         printf("%d %d ",lsum,rsum);
124         bfs();
125     }
126     return 0;
127 }