来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。

输入描述:

第一行两个整数N，M分别表示迷宫的行和列。

接下来一个N * M的矩阵，其中 "C" 表示小A的位置, "D" 表示小B的的位置，"＃" 表示不可通过的障碍， "." 则是可以正常通过的位置。字符用空格隔开，第>一行两个整数N，M分别表示迷宫的行和列。

输出描述:

如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。

否则就输出一个NO表示不能相遇。

输入

4 5

. . . . .

. # # # .

. . . # D

. . C # .

输出

YES

3

备注:
1 ≤ n, m ≤ 1000

解题思路

很明显的迷宫问题，用BFS搜索

开两个队列，两个vis数组记录两个人的路程，如果两个vis数组的同一个位置都被标记了，就说明相遇。如果两个队列都空了都没有相遇说明不可能。

另外说这道题的坑还是蛮多的

· 小B每次可以走两步的，所以简单粗暴bfs两次

· 输入时带空格，由于我一直用cin所以没啥影响

· 判定边界的时候把#这个点漏了可把孩子吓到了

· 必须两个队列都空才能判定是NO，&&和||别弄反了（哭

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
char Map[1007][1007];
queue<pair<int, int> > q[2];
bool vis[2][1007][1007];
int dx[10] = {0, 1, 0, -1, 0, 1, 1, -1, -1};
int dy[10] = {0, 0, 1, 0, -1, 1, -1, 1, -1};
bool bfs(int x){
    int len = q[x].size();
    while(len--){
        pair<int, int> p = q[x].front();
        q[x].pop();
        int l = 0;
        if(x == 0) l = 8;
        else l = 4;
        for(int i = 1; i <= l; i++){
            int xx = p.first + dx[i];
            int yy = p.second + dy[i];
            if(xx > 0 && xx <= n && yy > 0 && yy <= m && Map[xx][yy] != '#' && vis[x][xx][yy] == 0){
                if(vis[x ^ 1][xx][yy] == 1) return 1;
                vis[x][xx][yy] = 1;
                q[x].push(make_pair(xx, yy));
            }
        }
    }
    return 0;
}
int f(){
    int ans = 0;
    while(q[0].size() != 0 || q[1].size() != 0){
        ans++;
        if(bfs(0)) return ans;
        if(bfs(1)) return ans;
        if(bfs(1)) return ans;
    }
    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));
                vis[0][i][j] = 1;
            }
            if(Map[i][j] == 'D') {
                q[1].push(make_pair(i, j));
                vis[1][i][j] = 1;
            }
        }
    }
    int ans = f();
    if(ans == -1)
        cout << "NO";
    else
        cout << "YES" << endl << ans;
    return 0;
}

午安

End.