$BFS$搜索。
问题分三个，最后一个是最简单的$BFS$，不再赘述。
前两个问题更简单了，说要紧贴着左边的墙走，紧贴着右边的墙走，那么这种路肯定是唯一的，模拟找一下就可以了。
以紧贴着左边的墙走为例：
假设人目前0的朝向是右边，我要走下一步了，首先要判断的是可不可以左转，如果可以，那么左转。
如果不能左转，尝试着看看按原方向（右边）能不能走，如果可以走，那么走过去。
如果不能向右走，那么看看能不能右转（向下），如果可以那么向下走。
如果不能向下走，那么就返回（向左）。
就这样一直走下去，直到走到终点即可。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } const int maxn=100; int T,n,m,sx,sy,ex,ey,ans1,ans2,ans3; char s[maxn][maxn],g[maxn][maxn]; int dir[2][4][2]= { { {1,0},{0,1},{-1,0},{0,-1} }, { {1,0},{0,-1},{-1,0},{0,1} } }; struct X { int x,y,s; X(int xx,int yy,int ss) { x=xx; y=yy; s=ss; } }; bool F(int x,int y) { if(x<0||x>=n||y<0||y>=m||s[x][y]=='#') return 0; return 1; } int bfs() { queue<X>Q; Q.push(X(sx,sy,0)); g[sx][sy]=1; while(!Q.empty()) { X h=Q.front(); Q.pop(); if(s[h.x][h.y]=='E') return h.s; for(int i=0;i<4;i++) { int tx=h.x+dir[0][i][0], ty=h.y+dir[0][i][1]; if(!F(tx,ty)) continue; if(g[tx][ty]==1) continue; Q.push(X(tx,ty,h.s+1)); g[tx][ty]=1; } } } int work(int x,int y,int d,int flag) { int res=1; while(s[x][y]!='E') { int st=(d+1)%4,sz=0; int tmp[5]; for(int i=st;i>=0;i--) tmp[sz++]=i; for(int i=3;i>st;i--) tmp[sz++]=i; for(int i=0; i<4; i++) { int nx=tmp[i]; int tx=x+dir[flag][nx][0],ty=y+dir[flag][nx][1]; if(!F(tx,ty)) continue; x=tx; y=ty; d=nx; res++; break; } } return res; } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&m,&n); for(int i=0;i<n;i++) { scanf("%s",s[i]); for(int j=0;j<m;j++) if(s[i][j]=='S') sx=i,sy=j; } int d1,d2; for(int i=0;i<4;i++) { int tx=sx+dir[0][i][0],ty=sy+dir[0][i][1]; if(F(tx,ty)) d1=i; tx=sx+dir[1][i][0],ty=sy+dir[1][i][1]; if(F(tx,ty)) d2=i; } ans1=work(sx,sy,d1,0); ans2=work(sx,sy,d2,1); memset(g,0,sizeof g); ans3=bfs()+1; printf("%d %d %d ",ans1,ans2,ans3); } return 0; }