题目链接：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确定后，其转动的数组下标顺序也会一一对应。
代码：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#define mearv(a, b) memset(a, b, sizeof(a))
#define mestrc(a, b, c) memset(&(a), b, sizeof(c)) typedef long long LL;
using namespace std;
const int MAXN = ;
int map[MAXN + ][MAXN + ];
int w, h;
int stX, stY, edX, edY; //分别代表‘S’和‘E’的坐标
const int TURNLEFT = , TURNRIGHT = -; //rule = TURNLEFT 则以左转为优先 rule = TURNRIGHT 则以右转为优先
const int DOWN = , UP = , LEFT = , RIGHT = ;//statu （= DOWN 面向北方） （= UP 面向南方） (= LEFt 面向西方) (= RIGHT 面向东方)
const int stepX[] = {, -, , }; // 当面向北方时的 左、上、右、下 变换
const int stepY[] = {-, , , };
int ans;
int ok; void DFS(int x, int y, int status, int rule) {//当前位于坐标(x，y)处， 面向status 优先选择为 rule 利用DFS求左转步数和右转步数
if(ok) return;
if(x == edX && y == edY){ //到达出口
ok = ;
return;
}
else {
for(int i = (status + - rule) % , j = ; j < ; i %= , j++) {//当前方为status，优先选择为 rule时，所考虑的四个方向的顺序
int nex = x + stepX[i], ney = y + stepY[i];
if(map[nex][ney] == '.' || map[nex][ney] == 'E') {//是否可以走
++ans;
status = i;//每走一步，需要更新当前的方位，当前的方位和之前一步的方位相同
DFS(nex, ney, status, rule);
if(ok)return;
}
i += rule + ; //i有可能为负数
}
}
} typedef struct Point{int x; int y; int sp;}point; //走到坐标为( x, y)的地方的步数为 sp
void BFS(int stx, int sty) {//利用BFS求最短路径
queue<point> Qu;
point st;
st.x = stx; st.y = sty, st.sp = ;
Qu.push(st);//起点入队
while(!Qu.empty()) {
point tp = Qu.front();//选择当前扩展节点为队首元素
if(tp.x == edX && tp.y == edY) {//到达出口
ans = tp.sp;
break;
}
Qu.pop();
for(int i = ; i < ; i++) {//判断周围的4个邻接点
point nex;
nex.x = tp.x + stepX[i], nex.y = tp.y + stepY[i], nex.sp = tp.sp + ;//到子节点的步数等于到父节点的步数加1
if(map[nex.x][nex.y] == '.' || map[nex.x][nex.y] == 'E'){
Qu.push(nex);
map[nex.x][nex.y] = '$';//已走过标记，不能再走
}
}
} } int main() {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d", &w, &h);
mearv(map, );
stX = stY = edX = edY = -;
for(int i = ; i <= h; i++) {
getchar();
for(int j = ; j <= w; j++) {
scanf("%c", &map[i][j]);
if(map[i][j] == 'S') stX = i, stY = j;
if(map[i][j] == 'E') edX = i, edY = j;
}
}
int statu = -;
//判断刚开始的面向方位
if(stX == ) statu = DOWN;
if(stX == h) statu = UP;
if(stY == ) statu = LEFT;
if(stY == w) statu = RIGHT;
int rule = ; rule = TURNLEFT;//以左转优先
ans = , ok = ;
DFS(stX, stY, statu, rule);//求解
printf("%d ", ans); rule = TURNRIGHT;//以右转优先
ans = ; ok = ;
DFS(stX, stY, statu, rule);
printf("%d ", ans); ans = ; //最短路优先
BFS(stX, stY);
printf("%d\n", ans);
}
return ;
}