NC23486 小A与小B(双向BFS)牛客小白月赛13

54 阅读 0 评论 36 点赞

我是靠谱客的博主长情导师，最近开发中收集的这篇文章主要介绍NC23486 小A与小B(双向BFS)牛客小白月赛13，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://ac.nowcoder.com/acm/problem/23486
来源：牛客网

小A与小B
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。
输入描述:
第一行两个整数N，M分别表示迷宫的行和列。
接下来一个Ntimes M 的矩阵其中"C"表示小A的位置,"D"表示小B的的位置，
"＃“表示不可通过的障碍，”."则是可以正常通过的位置。字符用空格隔开第一行两个整数N，M分别表示迷宫的行和列。
接下来一个N×M的矩阵
其中"C"表示小A的位置,"D"表示小B的的位置，
"＃“表示不可通过的障碍，”."则是可以正常通过的位置。
字符用空格隔开

输出描述:
如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。
示例1
输入
复制
4 5
. . . . .
. # # # .
. . . # D
. . C # .
输出
复制
YES
3
备注:
$1 \leq n, m \leq 1000$

解题：双向bfs，（HDU3085）
这种情况很明显是用BFS方法搜索，复杂度是O(nm)
由于是两个人，所以进行双向BFS
将两个人的初始位置放入两个队列，记为第0秒
然后按各自的方向进行BFS搜索
由于小B可以走两次，直接BFS两次
然后分别用两个vis数组标记两个人走过的点
如果发现有一个走过的点另一个人也走过，说明相遇了
此时的时间就是最短相遇时间
如果发现两个人的队列都空了，还没发现他俩相遇，那就是不可能相遇了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<time.h>
#include<vector>
using namespace std;
#define ll long long

int n,m;
char Map[1010][1010];
int vis[2][1005][1005];  //0代表小A，1代表小B
int dir[8][2] = {-1,0,1,0,0,-1,0,1,-1,-1,1,-1,-1,1,1,1};
queue<pair<int,int>> q[2];	//queue队列


int bfs(int x)
{
    int sz = q[x].size();
    while(sz--){
        pair<int,int> p = q[x].front();
        q[x].pop();
        //A和B的方向不同，A有8个方向，B可以走4个方向
        for(int k=0; k<(x==1?4:8); ++k){
            int dx = p.first+dir[k][0];
            int dy = p.second+dir[k][1];
            if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&Map[dx][dy]!='#'&&!vis[x][dx][dy]){
                if(x==0&&vis[1][dx][dy])
                    return 1;  //相遇
                else if(x==1&&vis[0][dx][dy])
                    return 1;	//相遇
                vis[x][dx][dy] = 1;
                q[x].push(make_pair(dx,dy));
            }
        }
    }
    return 0;	//这步没有相遇
}

int solve()
{
    int res = 0;
    while(!q[0].empty()||!q[1].empty()){ 
    //只要不为空，就继续拓展
        res++;  //时间+1，1个时间内，A走一步，B走两步
        if(bfs(0)) return res;
        if(bfs(1)) return res;
        if(bfs(1)) return res;
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            cin>>Map[i][j];
            //起始位置入队列
            if(Map[i][j]=='C') q[0].push(make_pair(i,j));
            if(Map[i][j]=='D') q[1].push(make_pair(i,j));
        }
    }
    int ans = solve();
    if(ans==-1) cout<<"NO";
    else{
        cout<<"YES"<<endl;
        cout<<ans<<endl;
    }
    return 0;
}