100200H
这是个bfs
首先建图，先从终点bfs求出每点距离，然后从起点开始，确定初始方向：某点和自己相邻距离比自己小1就是
然后就先贪心和上次一样的方向，如果不能走，就找出一个方向，把自己当前方向改掉，重复过程，直到走到终点
#include<iostream> #include<queue> #include<cstdio> using namespace std; string s; const int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; int n,m; int can[410][410][5]; int used[410][410],d[410][410]; bool inrange(int x,int y) { return (x>=1&&y>=1&&x<=m&&y<=n); } void bfs() { queue<int>q; q.push(m); q.push(n); used[m][n]=1; while(!q.empty()) { int x=q.front(); q.pop(); int y=q.front(); q.pop(); for(int i=0;i<4;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(!used[xx][yy]&&inrange(xx,yy)&&can[x][y][i]) { d[xx][yy]=d[x][y]+1; q.push(xx); q.push(yy); used[xx][yy]=1; } } } } void get_path() { int x=1,y=1,last;//0:南 1：北 2：西 3：东 if(can[x][y][1]&&d[x][y]==d[x+dx[1]][y+dy[1]]+1) { x++; cout<<"N"<<endl; last=1; } else if(can[x][y][3]&&d[x][y]==d[x+dx[3]][y+dy[3]]+1) { y++; cout<<"E"<<endl; last=3; } while(x!=m||y!=n) { if(can[x][y][last]&&d[x+dx[last]][y+dy[last]]==d[x][y]-1) { x=x+dx[last]; y=y+dy[last]; cout<<"F"; } else for(int i=0;i<4;i++) { if(can[x][y][i]&&d[x+dx[i]][y+dy[i]]==d[x][y]-1) { x=x+dx[i]; y=y+dy[i]; if(last==0) { if(i==2) cout<<"R"; if(i==3) cout<<"L"; } if(last==1) { if(i==2) cout<<"L"; if(i==3) cout<<"R"; } if(last==2) { if(i==0) cout<<"L"; if(i==1) cout<<"R"; } if(last==3) { if(i==0) cout<<"R"; if(i==1) cout<<"L"; } last=i; break; } } } } int main() { freopen("straight.in","r",stdin); freopen("straight.out","w",stdout); scanf("%d%d",&m,&n); cin.ignore(); for(int i=m;i>=1;i--) { getline(cin,s,' '); for(int j=1;j<s.length();j+=2) { if(s[j]=='-') { can[i][(j+1)/2][3]=1; can[i][(j+2)/2+1][2]=1; } } if(i!=1) { getline(cin,s,' '); for(int j=0;j<s.length();j+=2) { if(s[j]=='|') { can[i][j/2+1][0]=1; can[i-1][j/2+1][1]=1; } } } } bfs(); get_path(); fclose(stdin); fclose(stdout); return 0; }