华尔兹

这题只需要从起点走到终点，所以选择bfs；

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,tx,ty;
int mp[1010][1010],vis[1000010],pre[1010][1010];//pre数组存放（x，y），（dx，dy）是由（x，y）转移过来的
int d[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
bool bfs()
{
    queue<int> q;
    q.push(sx*m+sy);
    vis[sx*m+sy]=1;
    while(!q.empty())
    {
        int k=q.front();q.pop();
        int x=k/m,y=k%m;
        if(x==tx&&y==ty) return 0;
        if(mp[x][y]==4)
        {
            for(int i=0;i<4;i++)
            {
                int dx=x+d[i][0],dy=y+d[i][1];
                if(dx>=n||dy>=m||dx<0||dy<0) continue;
                if(vis[dx*m+dy]) continue;
                vis[dx*m+dy]=1;
                pre[dx][dy]=x*m+y;
                q.push(dx*m+dy);
            }
        }
        else{
              int k=mp[x][y];
              int dx=x+d[k][0],dy=y+d[k][1];
              if(dx>=n||dy>=m||dx<0||dy<0) continue;
              if(vis[dx*m+dy]) continue;
              vis[dx*m+dy]=1;
              pre[dx][dy]=x*m+y;
              q.push(dx*m+dy);
        }
    }
}
int main()
{
    cin>>n>>m>>sx>>sy>>tx>>ty;
    sx--,sy--,tx--,ty--;//这里我是从0开始
    memset(mp,-1,sizeof(mp));
    memset(pre,-1,sizeof(pre));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            char ch;
            cin>>ch;
            if(ch=='w') mp[i][j]=3;
            if(ch=='s') mp[i][j]=0;
            if(ch=='a') mp[i][j]=2;
            if(ch=='d') mp[i][j]=1;
            if(ch=='.') mp[i][j]=4;
        }
    }
    bfs();
    int u=tx,v=ty;
    while(pre[u][v]!=-1)//反向复原路径
    {
        int k=pre[u][v];
        int x=k/m,y=k%m;
        if(x>u&&mp[x][y]==4) mp[x][y]=3;
        if(x<u&&mp[x][y]==4) mp[x][y]=0;
        if(y<v&&mp[x][y]==4) mp[x][y]=1;
        if(y>v&&mp[x][y]==4) mp[x][y]=2;
        u=x,v=y;
    }
    cout<<n<<' '<<m<<' '<<(sx+1)<<' '<<(sy+1)<<' '<<(tx+1)<<' '<<(ty+1)<<endl;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(mp[i][j]==3) cout<<'w';
            if(mp[i][j]==0) cout<<'s';
            if(mp[i][j]==2) cout<<'a';
            if(mp[i][j]==1) cout<<'d';
            if(mp[i][j]==4) cout<<'w';//对于这种（哪个方向都能走到终点）的结点，随意写个字母
        }
        cout<<endl;
    }
}