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