题目链接：http://poj.org/problem?id=3083
在这里感谢POJ上 xiexinxinlove大大的指导，以下摘取他对这道题的分析。
逆反起点求左右，脑洞真心大！佩服~orz
**注意三个问题：
* 1.使用DFS计算左转优先和右转优先的路径，使用BFS计算最短路径
* 2.这里的DFS不需要标记，因为按照方向顺时针（或逆时针）前进时，除非无路可走才会返回，所以不会因为没有标记而出现问题，不过它的前进方向是相对，是相对当前位置进行左上右下（右前左后）探索（这个相对性非常重要），最初的方向由起点S确定，而下一步的方向则由前一步的走向决定
以顺时针，左手优先为例，即（相对于当前方向，左转90°后的方向为第一优先，依次右转90°找可能的通路）
如何左转90度？0,1,2,3代表四个方向，显示直接-1是不行的，可能变成负值了，那么可以用
(d+3)%4,就可以左转90度到优先位置，当然往右转的过程中，还是会超过0,1,2,3，到了外面，所以在运算时，使用d%4就可以了。
* 3.起点到终点顺时针的话，它的逆时针也可以使用顺时针所使用的DFS，只要把起点和终点倒过来就可以了，也就是DFS可以共用。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int Max = 50;
int dir[4][2] = {
{0,-1},{-1,0},{0,1},{1,0}}; //以左上右下（顺时针）为基本方向数组
char map[Max][Max];
int vis[Max][Max];//广搜标记数组
int sx,sy,ex,ey;
int w,h,count,flag;
struct node
{int x,y;int dis;
}now,temp;
void dfs(int x, int y, int tx, int ty, int d)
{int nx,ny;if(x == tx && y == ty){flag = 1;return;} d = (d+3)%4; //在上一个方向的基础上，左转90度到优先位置int i = d; for(i=d; i<d+4; i++){nx = x + dir[i%4][0]; ny = y + dir[i%4][1];if(nx >= 0 && nx < h && ny >= 0 && ny < w && map[nx][ny] != '#'){count++;d = i; //记录当前方向 dfs(nx, ny, tx, ty, d);if(flag)return;}}
}
void bfs()
{queue<node> q;now.x = sx;now.y = sy;now.dis = 1;q.push(now);while(!q.empty()){now = q.front();q.pop();if(map[now.x][now.y] == 'E'){cout<<now.dis<<endl;return;} for(int i=0; i<4; i++){temp.x = now.x + dir[i][0];temp.y = now.y + dir[i][1];temp.dis = now.dis + 1;if(temp.x >=0 && temp.x <= h && temp.y >= 0 && temp.y < w && map[temp.x][temp.y] != '#' && !vis[temp.x][temp.y]){vis[temp.x][temp.y] = 1;q.push(temp);}}}
}
int main()
{int t;while(scanf("%d",&t) != EOF){while(t--){scanf("%d %d",&w,&h);for(int i=0; i<h; i++) //记住这里用h {getchar(); for(int j=0; j<w; j++) //记住这里用w { scanf("%c",&map[i][j]);if(map[i][j] == 'S'){ sx = i;sy = j;}if(map[i][j] == 'E'){ex = i;ey = j;}}}flag = 0;count = 1;dfs(sx, sy, ex, ey, 0); //顺时针,左手边,初始方向无所谓，因为只有1个出口，反正会调整好 cout<<count<<" ";flag = 0;count = 1;dfs(ex, ey, sx, sy, 0); //逆时针（右手边） cout<<count<<" ";memset(vis, 0, sizeof(vis)); bfs();}}return 0;
}