题目链接：http://poj.org/problem?id=3083
解题报告：这个题目，搜最短路，没有什么问题。优先走左边，走右边，有很多说法，思路大概都相同，都是记录当前朝向，根据数学公式(i+j+3)%4计算下一个方向，但是小草发现有些博客里面有一点点小错误，就是在方向的表示上。
左边优先，上右下左分别为0、1、2、4。dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
右边优先，左下右上分别为0、1、2、3。dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define MAXN 1000000007 #define judge(x,y) x>=0&&x<m&&y>=0&&y<n&&map[x][y]!='#'&&!vis[x][y] int dir1[4][2]= {{-1,0},{0,1},{1,0},{0,-1}}; ///左边优先 int dir2[4][2]= {{0,-1},{1,0},{0,1},{-1,0}}; ///右边优先 char map[45][45]; bool vis[45][45]; int m,n; struct node { int x,y; int dist; }; int step,START_I; int left_step=0,right_step=0; int DFS(int x,int y,int I,int di[][2]) { if(map[x][y]=='E') return 1; int i,j; for(j=0; j<4; j++) { i=(I+j+3)%4; if(judge(x+di[i][0],y+di[i][1])) { step=DFS(x+di[i][0],y+di[i][1],i,di)+1; break; } } return step; } int bfs(int x,int y) { memset(vis,0,sizeof(vis)); queue<node> q; node u; u.x=x; u.y=y; u.dist=0; vis[u.x][u.y]=true; q.push(u); while(!q.empty()) { u=q.front(); int d=u.dist; if(map[u.x][u.y]=='E') return u.dist; q.pop(); for(int i=0; i<4; i++) { node v; v.x=u.x+dir1[i][0]; v.y=u.y+dir1[i][1]; if(judge(v.x,v.y)) { vis[v.x][v.y]=true; v.dist=d+1; q.push(v); } } } return 0; } int main() { int cas; scanf("%d",&cas); while(cas--) { memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); int sx,sy; ///开始的坐标 for(int i=0; i<m; i++) { scanf("%s",map[i]); for(int j=0; j<n; j++) if(map[i][j]=='S') sx=i,sy=j; } ///一直向左走时，先找到出口的方向 for(int i=0; i<4; i++) if(judge(sx+dir1[i][0],sy+dir1[i][1])) ///从这个点搜四边，是否有出口，并且记录下来出口，上右下左分别为0,1,2,3, START_I=i; ///(i+j+3)%4 step=0; left_step=DFS(sx,sy,START_I,dir1); ///向右 for(int i=0; i<4; i++) if(judge(sx+dir2[i][0],sy+dir2[i][1])) ///从这个点搜四边，是否有出口，并且记录下来出口，左下右上分别为0,1,2,3， START_I=i; ///(i+j+3)%4 step=0; memset(vis,0,sizeof(vis)); right_step=DFS(sx,sy,START_I,dir2); printf("%d %d %d ",left_step,right_step,bfs(sx,sy)+1); } return 0; }