华尔兹

链接：https://ac.nowcoder.com/acm/problem/15204

题目描述：

有一个 n x m 大小的网格，其中有些格点比较特殊，当玩家站在上面的时候会自动移动到相邻四个方向之一，另外一些格点暂时还并不特殊，因为它们的移动方向还未知。 现在给定一个起点和一个终点，你需要给其中一些移动方向未知的格点确定一个方向，使得玩家能从起点移动到终点。

输入描述：

对于一个关卡，其对应的文件描述如下。
第一行六个空格隔开的整数 n,m,sx,sy,tx,ty，它们的意义分别如下：

• n 和 m 描述地图的大小，它们分别表示地图的行数、列数。
• sx,sy 分别表示起点的行、列坐标，即起点为第 sx 行第 sy 列的格点。（行、列的编号均从 1 开始）
• tx,ty 分别表示终点的行、列坐标，描述规则同上。
  接下来 n 行每行 m 个字符，每个字符表示网格对应位置的状态，不同字符的意义如下：
• w表示向上移动
• s表示向下移动
• a表示向左移动
• d表示向右移动
• .表示方向未确定

输出描述：

对于一个关卡，其对应的输出文件为将其输入文件中 . 替换为 w, a, s, d 中任意一个字符的结果，其余内容与格式不变。

solution：

这题可以先通过bfs，搜索出一条可以到终点的道路，如果是.那么对上下左右四个方向进行探索，w，s，a，d对对应的方向进行探索
找出那条路后，从起点开始进行反向探索，如果原来的点到现在的点距离差1（而不是-1），那么这个点处于到终点的那条路上，如果该点为.，再对其方向进行设置。

tips：要搞清楚行、列方向和wsda对应的方向，我就是卡在方向上了。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
int n,m,sx,sy,tx,ty;
char tu[1010][1010];
int d[1010][1010];
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};

void bfs()
{
    queue<P> q;
    d[sx][sy]=0;
    q.push(P(sx,sy));
    while(!q.empty())
    {
        P p=q.front();q.pop();
        if(tu[p.first][p.second]=='.')
        {
            for(int i=0;i<4;i++)
            {
                int x=p.first+dx[i],y=p.second+dy[i];
                if(x<0||x>=n||y<0||y>=m)continue;
                if(d[x][y]!=INF)continue;
                d[x][y]=d[p.first][p.second]+1;
                q.push(P(x,y));
            }
        }
        else if(tu[p.first][p.second]=='s')
        {
            int x=p.first+dx[0],y=p.second+dy[0];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(d[x][y]!=INF)continue;
            d[x][y]=d[p.first][p.second]+1;
            q.push(P(x,y));
        }
        else if(tu[p.first][p.second]=='w')
        {
            int x=p.first+dx[1],y=p.second+dy[1];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(d[x][y]!=INF)continue;
            d[x][y]=d[p.first][p.second]+1;
            q.push(P(x,y));
        }
        else if(tu[p.first][p.second]=='a')
        {
            int x=p.first+dx[2],y=p.second+dy[2];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(d[x][y]!=INF)continue;
            d[x][y]=d[p.first][p.second]+1;
            q.push(P(x,y));
        }
        else
        {
            int x=p.first+dx[3],y=p.second+dy[3];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(d[x][y]!=INF)continue;
            d[x][y]=d[p.first][p.second]+1;
            q.push(P(x,y));
        }
    }
}
void resettu()
{
    queue<P>q;
    q.push(P(tx,ty));
    while(!q.empty())
    {
        P p=q.front();q.pop();
        for(int i=0;i<4;i++)
        {
            int x=p.first+dx[i],y=p.second+dy[i];
            if(x<0||x>=n||y<0||y>=m)continue;
            if((d[x][y]+1)!=d[p.first][p.second])continue;
            char c;
            if(y-p.second==-1)
                c='d';
            else if(y-p.second==1)
                c='a';
            else if(x-p.first==-1)
                c='s';
            else
                c='w';
            if(tu[x][y]!='.'&&c!=tu[x][y])continue;
            tu[x][y]=c;
            q.push(P(x,y));
        }
    }
}
int main()
{
    cin>>n>>m>>sx>>sy>>tx>>ty;
    for(int i=0;i<n;i++)
        cin>>tu[i];
    memset(d,INF,sizeof(d));
    sx--;sy--;
    tx--;ty--;
    bfs();
    resettu();

    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(tu[i][j]=='.')
                cout<<'w';
            else
                cout<<tu[i][j];
        }
        cout<<endl;
    }
}