题意：
按照靠左走，靠右走以及最短路径的规则求从Ｓ点出发到Ｅ点的距离
方向有点难，因为当你改变方向的时候，下一步的方向也就随之改变了；
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #define N 100 using namespace std; int n,m,ex,ey,sx,sy; char str[N][N]; int map[N][N]; int d[4][2]= {{-1,0},{0,1},{1,0},{0,-1}}; int leftdfs(int x,int y,int ans,int p) { int i; if(x==ex&&y==ey) { cout<<ans<<' '; return true; } for(i=0; i<4; i++) { int np=(i+p+3)%4;/*按左走是左上右下的顺序*/ int nx=x+d[np][0],ny=y+d[np][1]; if(nx<0||nx>=n||ny<0||ny>=m||str[nx][ny]=='#') continue; if(leftdfs(nx,ny,ans+1,np)) return true; } return false; } int rightdfs(int x,int y,int ans,int p) { int i; if(x==ex&&y==ey) { cout<<ans<<' '; return true; } for(i=3; i>=0; i--) { int np=(i+2+p)%4;/*按右走是右上左下*/ int nx=x+d[np][0],ny=y+d[np][1]; if(nx<0||nx>=n||ny<0||ny>=m||str[nx][ny]=='#') continue; if(rightdfs(nx,ny,ans+1,np)) return true; } return false; } void bfs(int x,int y) { int i,j; for(i=0; i<N; i++) for(j=0; j<N; j++) map[i][j]=0; typedef pair<int,int> P; queue <P>q; q.push(P(x,y)); map[sx][sy]=1; while(q.size()) { P f=q.front(); q.pop(); if(f.first==ex&&f.second==ey) { cout<<map[ex][ey]<<endl; return; } for(i=0; i<4; i++) { int nx=f.first+d[i][0],ny=f.second+d[i][1]; if(nx<0||nx>=n||ny<0||ny>=m||str[nx][ny]=='#'||map[nx][ny])/*第一遍的时候忘了检查map[nx][ny]是否遍历过TLE*/ continue; q.push(P(nx,ny)); map[nx][ny]=map[f.first][f.second]+1; } } } int main() { int t,i; cin>>t; while(t--) { ex=ey=sx=sy=-1; scanf("%d%d%*c",&m,&n); int p=0; for(i=0; i<n; i++) { scanf("%s",str[i]); for(int j=0; j<m; j++) { if(sx!=-1&&ex!=-1) break; if(str[i][j]=='S') sx=i,sy=j; else if(str[i][j]=='E') ex=i,ey=j; } } leftdfs(sx,sy,1,0); rightdfs(sx,sy,1,0); bfs(sx,sy); } return 0; }