POJ3083 Children of the Candy Corn(BFS+DFS)

题意：

普通的迷宫求路径，但这题需要输出三个解：1.沿着左边查找，2.沿着右边查找，3.最短路径

要点：

最短的简单，直接BFS搞定。沿着左边查找和沿着右边查找其实是一个问题，也即是DFS中先遍历左边还是右边，沿着左边查找就把顺时针查找，如果不成功就向右查找，向右查找一次其实是向前，两次向右，三次向后，反之同理。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
char maze[45][45];
int visit[45][45];
int m, n,ans;
int d[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//这个是固定的，左右都一样，写一下就可以看出来
struct node
{int x, y;int count;
};int ldfs(int x,int y,int step)
{if (maze[x][y] == 'E')return step + 1;if (x < 0 || x >= m || y < 0 || y >= n || maze[x][y]=='#')return 0;ans = (ans + 3) % 4; //左转的方向int temp = 0;while (1){temp=ldfs(x + d[ans][0], y + d[ans][1], step + 1);if (temp > 0)break;ans = (ans + 1) % 4;  //如果不行就右转，右转一次向前，如果向前还不行再右转，可以右转或后转}return temp;
}
int rdfs(int x,int y,int step)
{if (maze[x][y] == 'E')return step + 1;if (x < 0 || x >= m || y < 0 || y >= n || maze[x][y] == '#')return 0;ans = (ans + 1) % 4;int temp = 0;while (1){temp = rdfs(x + d[ans][0], y + d[ans][1], step + 1);if (temp > 0)break;ans = (ans + 3) % 4;}return temp;
}
int bfs(int x,int y)
{memset(visit, 0, sizeof(visit));queue<node> q;node u;u.x = x; u.y = y;u.count = 1;visit[x][y] = 1;q.push(u);while (!q.empty()){u = q.front();q.pop();node v;if (maze[u.x][u.y] == 'E')return u.count;for (int i = 0; i < 4; i++){v.x = u.x + d[i][0];v.y = u.y + d[i][1];if (!visit[v.x][v.y] && v.x >= 0 && v.x < m&&v.y >= 0 && v.y < n&&maze[v.x][v.y]!='#'){v.count = u.count + 1;q.push(v);visit[v.x][v.y] = 1;}}}
}int main()
{int t,i,j,di,dj;scanf("%d", &t);while (t--){scanf("%d%d", &n, &m);for (i = 0; i < m; i++){scanf("%s", maze[i]);for (j = 0; j < n;j++)if (maze[i][j] == 'S'){di = i;dj = j;}}ans = 0;   //每次方向默认向前printf("%d ", ldfs(di, dj, 0));ans = 0;printf("%d ", rdfs(di, dj, 0));printf("%d\n", bfs(di, dj));}return 0;
}