【题意】给定n*m的网格，起点和终点位置，一些格指定下一步的方向，一些格任意。要求为方向任意的格确定方向，使起点可以走到终点。n,m<=50。

【算法】BFS

【题解】这道题最好用BFS，因为DFS容易陷入死路。

BFS过程中访问过的点标记vis，记录前驱后不用再访问，这是由于：

由于路径不可能走环，所以实际上可以忽略路径自身的影响，只保留能到达某个点的信息，最终到达终点（即访问过的点无需再访问）。

#include
      
       #include
       
        #include
        
         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
         
          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",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;}