华尔兹(BFS)

  • 时间:
  • 来源:互联网
  • 文章标签:

链接: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 中任意一个字符的结果,其余内容与格式不变。
    示例1
    输入
    复制
    4 4 1 1 4 4
    .aaa
    .www
    .sss

    输出
    复制
    4 4 1 1 4 4
    saaa
    swww
    dsss
    dddw

题意:略

题记:BFS一下走到终点的路径,记录下走的方向,最后从终点返回起点把方向存进原来的地图中。

#include<bits/stdc++.h>

using namespace std;
const int N=1010;
int n,m,sx,sy,tx,ty;
char a[N][N];
int vis[N][N];
int dis[5][2]={0,0,-1,0,1,0,0,-1,0,1};//上下左右
struct Node{
    int x,y;
};

bool check(int x,int y){
    if(x<1||x>n||y<1||y>m||vis[x][y])
        return false;
    return true;
}

int f(int x,int y){
    if(a[x][y]=='w')
        return 1;
    else if(a[x][y]=='s')
        return 2;
    else if(a[x][y]=='a')
        return 3;
    else if(a[x][y]=='d')
        return 4;
}

void bfs(int dx,int dy){
    Node st,ne;
    queue<Node>q;
    st.x=dx,st.y=dy;
    vis[dx][dy]=1;
    q.push(st);
    while(!q.empty()){
        st=q.front();
        q.pop();
        int x=st.x,y=st.y;
        //cout<<x<<' '<<y<<endl;
        if(x==tx&&y==ty)
            break;
        if(a[x][y]=='.'){
            for(int i=1;i<=4;i++){
                ne.x=st.x+dis[i][0];
                ne.y=st.y+dis[i][1];
                if(check(ne.x,ne.y)){
                    vis[ne.x][ne.y]=i;
                    q.push(ne);
                }
            }
        }
        else{
            int pos=f(x,y);
            ne.x=st.x+dis[pos][0];
            ne.y=st.y+dis[pos][1];
            if(check(ne.x,ne.y)){
                vis[ne.x][ne.y]=pos;
                q.push(ne);
            }
        }
    }
}

int main(){
    cin>>n>>m>>sx>>sy>>tx>>ty;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    bfs(sx,sy);
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<vis[i][j]<<' ';
        cout<<endl;
    }
    */
    int x=tx,y=ty;
    while(x!=sx||y!=sy){
        int dx=x-dis[vis[x][y]][0];
        int dy=y-dis[vis[x][y]][1];
        if(vis[x][y]==1) a[dx][dy]='w';
        else if(vis[x][y]==2) a[dx][dy]='s';
        else if(vis[x][y]==3) a[dx][dy]='a';
        else if(vis[x][y]==4) a[dx][dy]='d';
        x=dx;
        y=dy;
    }
    cout<<n<<' '<<m<<' '<<sx<<' '<<sy<<' '<<tx<<' '<<ty<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='.') cout<<'w';
            else cout<<a[i][j];
        }
        cout<<endl;
    }
    return 0;
}

本文链接http://www.taodudu.cc/news/show-82965.html