【题意】给定n*m的网格，起点和终点位置，一些格指定下一步的方向，一些格任意。要求为方向任意的格确定方向，使起点可以走到终点。n,m<=50。
【算法】BFS
【题解】这道题最好用BFS，因为DFS容易陷入死路。
BFS过程中访问过的点标记vis，记录前驱后不用再访问，这是由于：
由于路径不可能走环，所以实际上可以忽略路径自身的影响，只保留能到达某个点的信息，最终到达终点（即访问过的点无需再访问）。
#include<cstdio> #include<queue> #include<algorithm> using namespace std; const int maxn=1010; const int fx[]={0,0,0,1,-1}; const int fy[]={0,1,-1,0,0}; int n,m,sx,sy,tx,ty,map[maxn][maxn],p[maxn][maxn]; bool v[maxn][maxn]; char s[maxn]; queue<int>Q; bool c(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m&&!v[x][y];} int main(){ scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty); for(int i=1;i<=n;i++){ scanf("%s",s+1); for(int j=1;j<=m;j++){ if(s[j]=='.')map[i][j]=0; if(s[j]=='d')map[i][j]=1; if(s[j]=='a')map[i][j]=2; if(s[j]=='s')map[i][j]=3; if(s[j]=='w')map[i][j]=4; } } Q.push(sx);Q.push(sy);v[sx][sy]=1; while(!Q.empty()){ int x=Q.front();Q.pop(); int y=Q.front();Q.pop(); if(x==tx&&y==ty)break; if(map[x][y]>0){ int X=x+fx[map[x][y]],Y=y+fy[map[x][y]]; if(c(X,Y))Q.push(X),Q.push(Y),p[X][Y]=map[x][y],v[X][Y]=1; } else{ for(int i=1;i<=4;i++){ int X=x+fx[i],Y=y+fy[i]; if(c(X,Y))Q.push(X),Q.push(Y),p[X][Y]=i,v[X][Y]=1; } } } int x=tx,y=ty; while(x!=sx||y!=sy){ int X=x-fx[p[x][y]],Y=y-fy[p[x][y]];// map[X][Y]=p[x][y]; x=X;y=Y; } printf("%d %d %d %d %d %d ",n,m,sx,sy,tx,ty); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(map[i][j]==0||map[i][j]==1)printf("d"); if(map[i][j]==2)printf("a"); if(map[i][j]==3)printf("s"); if(map[i][j]==4)printf("w"); } puts(""); } return 0; }