题目链接：http://poj.org/problem?id=3083
题意：
这里有一个w * h的迷宫，给你入口和出口，让你分别求以下三种情况时，到达出口的步数(总步数包括入口和出口)：
第一种：当你需要选择下一个位置时，总是需要这么考虑：如果当前的左方能走，那么就走左方;否则考虑前方是否能走，如果能走，那么就选前方;否则考虑右方是否能走，如果可以，就走右方。如果不能就返回上一个位置，即当前位置的后方。总结下来选择道路的优先顺序为(以当前所处方位为准) 左 -> 上(前) -> 右 -> 下(后)。走过的路可以重复走，即走到死胡同了就可以原路返回了。
第二种：与第一种差不多，仅仅是从右边开始考虑。选择道路的顺序为 右 -> 上(前) -> 左 -> 下(后)。
第三种： 求从出口到入口的最短距离。
出口和入口在迷宫的边缘，分别用“E”和“S”代表。“#”代表墙，“.”代表可以走的路。"E" 和 “S”之间肯定会存在一个 “#”,且都不会出现在角落，保证问题有解。
思路及做法：
处理第一种和第二种利用DFS,处理第三种的最短路径利用BFS. BFS的最短路径直接寻找就好，不用考虑方位。这里就着重解释下利用DFS来寻找第一种和第二种情况的解。
首先利用一个不变的方位来阐述，假设以给出的图上方为北， 以下方为南， 以左方为西， 以右方为东，因为这四个方位始终都不变，比较好理解。
1
0 @ 2
3
假设此时人正处于“@”处，此时面向北方(”1“方位)，“0“ 方位为 西方， ”1“ 方位为北方， ”2“方位为东方， ”3“方位为南方。假设此时的”@“的坐标为(0, 0),规定向下为x增大的方向， 向右为y增大的方向，则到”0“方位去的方法是给坐标加上(0, -1), 同理，到”1“方位加上(-1, 0),到”2“方位加(0,1)，到”3“方位加上(1,0).那么可以定义两个数组：
const int stepX[] = {0, -1, 0, 1};
const int stepY[] = {-1, 0, 1, 0};
当面向北方时，i=0代表左转，i=1代表不改变方向直接往前走;i=2代表右转;i=3代表往回走，向后转。这是一个基准，其他各种情况需要以这个为基础。
这个数组确定下来之后，就需要考虑每种情况下选择路时这个数组的下标的顺序。
定义变量 rule 代表是按照第一种情况考虑(rule = 1)还是第二种情况考虑(rule = -1).
定义变量 statu 代表当前面对的方向, statu = 1(此时面向北方) ，statu = 0(此时面向西方)，statu = 2(面向东方)，statu = 3(面向南方)
第一种情况(rule = 1， 即左转优先)
statu = 1(面向北方)
遇到路时的选择顺序： 左转 直走 右转 后转
基准数组下标的变化顺序： 0 1 2 3
statu = 0(面向西方，此时南方为左边)
遇到路时的选择顺序： 左转 直走 右转 后转
基准数组下标的变化顺序： 3 0 1 2
statu = 3(面向南方，此时东方为左边)
遇到路时的选择顺序： 左转 直走 右转 后转
基准数组下标的变化顺序： 2 3 0 1
statu = 2(面向东方，此时北方为左边)
遇到路时的选择顺序： 左转 直走 右转 后转
基准数组下标的变化顺序： 1 2 3 0
第二种情况(rule = -1,即右转优先)
statu = 1(面向北方)
遇到路时的选择顺序： 右转 直走 左转 后转
基准数组下标的变化顺序： 2 1 0 3
statu = 0(面向西方，此时北方为右边)
遇到路时的选择顺序： 右转 直走 左转 后转
基准数组下标的变化顺序： 1 0 3 2
statu = 3(面向南方，此时西方为右边)
遇到路时的选择顺序： 右转 直走 左转 后转
基准数组下标的变化顺序： 0 3 2 1
statu = 2(面向东方，此时南方为右边)
遇到路时的选择顺序： 右转 直走 左转 后转
基准数组下标的变化顺序： 3 2 1 0
大体的看上去，变化似乎没有规律可循，这样会复杂化程序，仔细找找，发现还是有规律的。
左转时(rule = 1)
statu = 1 -> 0 1 2 3
statu = 2 -> 1 2 3 0
statu = 3 -> 2 3 0 1
statu = 0 -> 3 0 1 2
可以看出后一个数等于前一个数加1对4取模。
右转时(rule = -1)
statu = 1 -> 2 1 0 3
statu = 0 -> 1 0 3 2
statu = 3 -> 0 3 2 1
statu = 2 -> 3 2 1 0
可以看出后一个数等于前一个数减1对4取模。
可以找到一个对应关系，使得 statu 和 rule确定后，第一个下标顺序 i 也会确定 i = (statu - rule + 4) % 4, 随后加1或者减1，循环变化四次就可以了。
for( i = (statu + 4 - rule) % 4 ; ; i %= 4){
i +=rule + 4;(rule 为1, 每次加1, rule为-1,每次减1, 加4是为了变负为正，继续循环)
}
上述关系就可以实现当statu 和 rule确定后，其转动的数组下标顺序也会一一对应。
代码：
1 #include <iostream> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <algorithm> 10 #include <string> 11 #define mearv(a, b) memset(a, b, sizeof(a)) 12 #define mestrc(a, b, c) memset(&(a), b, sizeof(c)) 13 14 typedef long long LL; 15 using namespace std; 16 const int MAXN = 40; 17 int map[MAXN + 7][MAXN + 7]; 18 int w, h; 19 int stX, stY, edX, edY; //分别代表‘S’和‘E’的坐标 20 const int TURNLEFT = 1, TURNRIGHT = -1; //rule = TURNLEFT 则以左转为优先 rule = TURNRIGHT 则以右转为优先 21 const int DOWN = 3, UP = 1, LEFT = 0, RIGHT = 2;//statu （= DOWN 面向北方） （= UP 面向南方） (= LEFt 面向西方) (= RIGHT 面向东方) 22 const int stepX[] = {0, -1, 0, 1}; // 当面向北方时的 左、上、右、下 变换 23 const int stepY[] = {-1, 0, 1, 0}; 24 int ans; 25 int ok; 26 27 void DFS(int x, int y, int status, int rule) {//当前位于坐标(x，y)处， 面向status 优先选择为 rule 利用DFS求左转步数和右转步数 28 if(ok) return; 29 if(x == edX && y == edY){ //到达出口 30 ok = 1; 31 return; 32 } 33 else { 34 for(int i = (status + 4 - rule) % 4, j = 0; j < 4; i %= 4, j++) {//当前方为status，优先选择为 rule时，所考虑的四个方向的顺序 35 int nex = x + stepX[i], ney = y + stepY[i]; 36 if(map[nex][ney] == ‘.‘ || map[nex][ney] == ‘E‘) {//是否可以走 37 ++ans; 38 status = i;//每走一步，需要更新前方的方位，目前的方位和之前一步的方位相同 39 DFS(nex, ney, status, rule); 40 if(ok)return; 41 } 42 i += rule + 4; //i有可能为负数 43 } 44 } 45 } 46 47 typedef struct Point{int x; int y; int sp;}point; //走到坐标为( x, y)的地方的步数为 sp 48 void BFS(int stx, int sty) {//利用BFS求最短路径 49 queue<point> Qu; 50 point st; 51 st.x = stx; st.y = sty, st.sp = 1; 52 Qu.push(st);//起点入队 53 while(!Qu.empty()) { 54 point tp = Qu.front();//选择当前扩展节点为队首元素 55 if(tp.x == edX && tp.y == edY) {//到达出口 56 ans = tp.sp; 57 break; 58 } 59 Qu.pop(); 60 for(int i = 0; i < 4; i++) {//判断周围的4个邻接点 61 point nex; 62 nex.x = tp.x + stepX[i], nex.y = tp.y + stepY[i], nex.sp = tp.sp + 1;//到子节点的步数等于到父节点的步数加1 63 if(map[nex.x][nex.y] == ‘.‘ || map[nex.x][nex.y] == ‘E‘){ 64 Qu.push(nex); 65 map[nex.x][nex.y] = ‘$‘;//已走过标记，不能再走 66 } 67 } 68 } 69 70 } 71 72 int main() { 73 //freopen("input", "r", stdin); 74 //freopen("output", "w", stdout); 75 int T; 76 scanf("%d", &T); 77 while(T--){ 78 scanf("%d%d", &w, &h); 79 mearv(map, 0); 80 stX = stY = edX = edY = -1; 81 for(int i = 1; i <= h; i++) { 82 getchar(); 83 for(int j = 1; j <= w; j++) { 84 scanf("%c", &map[i][j]); 85 if(map[i][j] == ‘S‘) stX = i, stY = j; 86 if(map[i][j] == ‘E‘) edX = i, edY = j; 87 } 88 } 89 int statu = -1; 90 //判断刚开始的面向方位 91 if(stX == 1) statu = DOWN; 92 if(stX == h) statu = UP; 93 if(stY == 1) statu = LEFT; 94 if(stY == w) statu = RIGHT; 95 int rule = 0; 96 97 rule = TURNLEFT;//以左转优先 98 ans = 1, ok = 0; 99 DFS(stX, stY, statu, rule);//求解 100 printf("%d ", ans); 101 102 rule = TURNRIGHT;//以右转优先 103 ans = 1; ok = 0; 104 DFS(stX, stY, statu, rule); 105 printf("%d ", ans); 106 107 ans = 0; //最短路优先 108 BFS(stX, stY); 109 printf("%d\n", ans); 110 } 111 return 0; 112 }
POJ 3083 Children of the Candy Corn (DFS + BFS + 模拟)
原文：http://www.cnblogs.com/Ash-ly/p/5719336.html