POJ3083 Children of the Candy Corn（Bfs + Dfs)

题意：给一个w*h的迷宫，其中矩阵里面 S是起点，E是终点，“#”不可走，“.”可走，而且，S、E都只会在边界并且，不会在角落，例如（0，0），输出的话，每组数据就输出三个整数，第一个整数，指的是，以S的起点为当前所对着的路径为正方向，如果正方向的左边能走的话，就走左边，不能就按正方向走，不行的话就就往回走，如此反复，记录步数，并输出，第二个整数也是如此，只不过搜的方向改成正方向的右边。第三个就是最短路，

分析：前两个用DFS求出，最短路直接BFS解决，，

单就沿着左走看一下：

当前方向　　检索顺序

Sx=n-1 ↑ ：　　← ↑ → ↓

Sy=0 → ：　 ↑ → ↓ ←

Sx=0 ↓ ：　　→ ↓ ← ↑

Sy=n-1 ← ：　 ↓ ← ↑ →

如此，规律很明显，假设数组存放方向为 ← ↑ → ↓，如果当前方向为 ↑，就从 ← 开始依次遍历，找到可以走的，如果 ← 可以走，就不用再看 ↑ 了。

这个题的麻烦处理就在于怎么按什么样的顺序dfs

在网上搜题解感觉这种想法特别好，不繁琐，代码还简洁

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 
  6 using namespace std;
  7 
  8 int dx[4]={0,-1,0,1};
  9 int dy[4]={-1,0,1,0};
 10 
 11 int dl[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
 12 int dr[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
 13 
 14 int sx,sy,ex,ey,n,m;
 15 char G[110][110];
 16 
 17 struct node
 18 {
 19     int x,y,s;
 20 };
 21 
 22 int dfs(int x,int y,int d,int step,int dir[4][2])
 23 {
 24     for(int i=0;i<4;++i)
 25     {
 26         int j=((d-1+4)%4+i)%4;
 27         int nx=x+dir[j][0];
 28         int ny=y+dir[j][1];
 29         if(nx==ex&&ny==ey)
 30             return step+1;
 31         if(nx<0||ny<0||nx>n||ny>m||G[nx][ny]=='#')
 32             continue;
 33         return dfs(nx,ny,j,step+1,dir);
 34     }
 35 }
 36 
 37 int BFS(int sx,int sy)
 38 {
 39     bool vis[110][110];
 40     memset(vis, false, sizeof(vis));
 41     queue<node>q;
 42     node a;
 43     a.x=sx,a.y=sy,a.s=1;
 44     q.push(a);
 45     vis[sx][sy]=true;
 46     while(!q.empty())
 47     {
 48         node p=q.front();
 49         q.pop();
 50         if(p.x==ex&&p.y==ey)
 51             return p.s;
 52         node p1;
 53         for(int i=0;i<4;++i) {
 54             p1.x=p.x+dx[i];
 55             p1.y=p.y+dy[i];
 56             p1.s=p.s+1;
 57             if(p1.x<0||p1.x>n||p1.y<0||p1.y>m||vis[p1.x][p1.y])
 58                continue;
 59             if(G[p1.x][p1.y]!='#')
 60             {
 61                 vis[p1.x][p1.y]=true;
 62                 q.push(p1);
 63             }
 64         }
 65     }
 66     return -1;
 67 }
 68 
 69 int main()
 70 {
 71     int T,d1,d2;
 72     scanf("%d",&T);
 73     while(T--)
 74     {
 75         scanf("%d%d",&m,&n);
 76         for(int i=0;i<n;++i)
 77         {
 78             scanf("%s",G[i]);
 79             for(int j=0;j<m;++j)
 80             {
 81                 if(G[i][j]=='S')
 82                 {
 83                     sx=i;
 84                     sy=j;
 85                 }
 86                 else if(G[i][j]=='E')
 87                 {
 88                     ex=i;
 89                     ey=j;
 90                 }
 91             }
 92         }
 93         if(sx==0)
 94         {
 95             d1=3;
 96             d2=3;
 97         }
 98         else if(sx==n-1)
 99         {
100             d1=1;
101             d2=1;
102         }
103         else if(sy==0)
104         {
105             d1=2;
106             d2=0;
107         }
108         else if(sy==m-1)
109         {
110             d1=0;
111             d2=2;
112         }
113         printf("%d ",dfs(sx,sy,d1,1,dl));
114         printf("%d ",dfs(sx,sy,d2,1,dr));
115         printf("%d
",BFS(sx,sy));
116     }
117     return 0;
118 }