Children of the Candy Corn

S为起点，E为中点，输出S—>E沿左边走的步数，沿右边走的步数，和最短步数。

因为S—>E沿左边走的步数等于E—>S沿右边走的步数，故只需DFS搜索沿右边走的步数，改变起止点即可。

然后BFS搜索最少步数。

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <queue>
 4 #include <string.h>
 5 
 6 using namespace std;
 7 const int N=55;
 8 char map[N][N];
 9 int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};//顺时针方向
10 int step1[N][N];//记录步数
11 
12 struct node
13 {
14     int x;
15     int y;
16 };
17 int DFS(int i,int j,int step,int d,char ss)//沿右边走
18 {
19     if (map[i][j]== ss) return step;
20     for (int k = d+4; k > d; k --)
21     {
22         int di = i + dir[k%4][0];
23         int dj = j + dir[k%4][1];
24         if (map[di][dj]!='#')
25             return DFS(di,dj,step+1,(k+1)%4,ss);
26     }
27     return -1;
28 }
29 int BFS(int i,int j)//计算最短步数
30 {
31     queue<node> q;
32     node  t;
33     t.x=i,t.y=j;
34     q.push(t);
35     step1[t.x][t.y]=1;
36     while(!q.empty())
37     {
38         t=q.front();
39         q.pop();
40         if(map[t.x][t.y]=='E')return step1[t.x][t.y];
41         node temp;
42         for(int d=0; d<4; ++d)
43         {
44             temp=t;
45             temp.x+=dir[d][0];
46             temp.y+=dir[d][1];
47             if(map[temp.x][temp.y]!='#' && !step1[temp.x][temp.y])
48             {
49                 q.push(temp);
50                 step1[temp.x][temp.y]=step1[t.x][t.y]+1;
51             }
52         }
53     }
54     return -1;
55 }
56 int main()
57 {
58     int T,col,row;
59     scanf("%d",&T);
60     while(T--)
61     {
62         scanf("%d%d%*c",&col,&row);
63         int s_i,s_j,e_i,e_j;
64         memset(step1,0,sizeof(step1));
65         memset(map,'#',sizeof(map));
66 
67         for (int i = 1; i <= row; i ++)
68         {
69             for (int j = 1; j <= col; j ++)
70             {
71                 scanf("%c",&map[i][j]);
72                 if (map[i][j]=='S')
73                 {
74                     s_i = i;
75                     s_j = j;
76                 }
77                 if (map[i][j]=='E')
78                 {
79                     e_i = i;
80                     e_j = j;
81                 }
82             }
83             getchar();
84         }
85         int ansl = DFS(e_i,e_j,1,0,'S');//E——>S沿右边走的步数，也是S——>E沿左边走的步数
86         int ansr = DFS(s_i,s_j,1,0,'E');//S——>E沿右边走的步数
87         int minstep = BFS(s_i,s_j);//S—— E的最少步数
88         printf("%d %d %d
",ansl,ansr,minstep);
89     }
90     return 0;
91 }

View Code