Children of the Candy Corn(BFS+DFS POJ3083)

~题目链接~

Sample Input

2
8 8
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E####
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########

Sample Output

37 5 5
17 17 9

DFS 进行左转和右转的数目统计

BFS 进行最短路的查找

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<queue>
 5 #define maxn 50
 6 
 7 using namespace std;
 8 
 9 int map[maxn][maxn],sp[maxn][maxn],n,m;
10 int f[4][2]= {{-1,0},{0,-1},{1,0},{0,1}};
11 
12 struct node
13 {
14     int x,y;
15 } S,E;
16 
17 queue<node>Q;
18 
19 int DFS(int x1,int y1,int x2,int y2,int sn,int step)
20 {
21     if(x1==x2 && y1==y2)
22         return step;
23     sn=(sn+1)%4;
24     while(!map[x1+f[sn][0]][y1+f[sn][1]])
25         sn=(sn+3)%4;
26     step++;
27     return DFS(x1+f[sn][0],y1+f[sn][1],x2,y2,sn,step);
28 }
29 
30 int BFS(struct node S,struct node E)
31 {
32     while(!Q.empty())
33         Q.pop();
34     Q.push(S);
35     sp[S.x][S.y]=1;
36     while(!Q.empty())
37     {
38         struct node V;
39         S=Q.front();
40         for(int i=0; i<4; i++)
41         {
42             V.x=S.x+f[i][0];
43             V.y=S.y+f[i][1];
44             if(V.x<0 || V.x>=m || V.y<0 || V.y>=n)
45                 continue;
46             if(!sp[V.x][V.y] && map[V.x][V.y])
47             {
48                 sp[V.x][V.y]=sp[S.x][S.y]+1;
49                 Q.push(V);
50             }
51             if(V.x==E.x && V.y==E.y && map[V.x][V.y])
52                 return sp[V.x][V.y];
53         }
54         Q.pop();
55     }
56 }
57 
58 int main()
59 {
60     int T;
61     scanf("%d",&T);
62     while(T--)
63     {
64         int i,j;
65         char c;
66         scanf("%d%d",&n,&m);
67         memset(map,0,sizeof(map));
68         memset(sp,0,sizeof(sp));
69         getchar();
70         for(i=0; i<m; i++)
71         {
72             for(j=0; j<n; j++)
73             {
74                 scanf("%c",&c);
75                 if(c=='.' || c=='S' || c=='E')
76                     map[i][j]=1;
77                 if(c=='S')
78                 {
79                     S.x=i;
80                     S.y=j;
81                 }
82                 if(c=='E')
83                 {
84                     E.x=i;
85                     E.y=j;
86                 }
87             }
88             getchar();
89         }
90         int l=DFS(S.x,S.y,E.x,E.y,1,1);//左转 从入到出深度优先遍历
91         int r=DFS(E.x,E.y,S.x,S.y,1,1);//右转 从出到入深度优先遍历
92         int k=BFS(S,E);//最短路 广度优先遍历
93         printf("%d %d %d
",l,r,k);
94     }
95 
96     return 0;
97 }

View Code