题目

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

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

输出描述：
如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。

解析

1）知识点

这道题是一道有点复杂的bfs，这里是双向广搜。

2）看题目

题目简单来说就是，按地图走路，两个人的走路方法也不一样，问两个人能不能相遇，相遇的最短回合数是多少。

3）算法分析

  1. 这道题难就难在，两个人的走路方法是不一样的。如果两个人的走路方法是一样的，我们可以求出两个人之间的距离，然后除3就好了。
  2. 但是现在是不一样的。我们这里就可以分两个人bfs（用点技巧可以合并成一个bfs，这一点先不管）。
  3. 现在我们知道的是，a可以走8个方向，每回合一步。b可以走四个方向，每回合两步。
  4. 也就是说我们不考虑走路方法的话，每回合就是让a走一步，让b走两步： 
    if (bfs(0)) return step;
//a走一次
if (bfs(1)) return step;
if (bfs(1)) return step;
//b走两次
//这里bfs用来判断，a和b是否在这一回合会碰到对方。
  5. 然后问题就是bfs怎么实现了。
  6. 其实和我们原来普通的bfs是差不多的，判定条件就是是否到达过了对面到达过的地方。

4）算法操作

  1. 首先就是走路的函数，用来计算到底走了多少次： 
    int calc() {
    int step = 1;
    while (!que[0].empty() || !que[1].empty()) {
        if (bfs(0)) return step;
        //a走一次
        if (bfs(1)) return step;
        if (bfs(1)) return step;
        //b走两次
        //判别成功表示相遇了
        step++;
    }
    return -1;
}
  2. 然后呢，我们就可以开始写bfs函数了。在那之前，我们先写一下bfs越界和走过的位置的判断函数： 
    bool judge(Node x, int res) {
    if (!mp[x.x][x.y]) return false;//用的是有边框的地图，所以可以减少特判
    if (vis[x.x][x.y][res]) return false;
    return true;
}
  3. 最后我们正常的来一遍bfs就可以啦： 
    bool bfs(int x) {
    int T = que[x].size();//消耗掉原来的步数
    while (T--) {
        Node top = que[x].front(); que[x].pop();
        for (int i = 0; i < 8 - 4 * x; i++) {
            Node nxt;
            nxt.x = top.x + walk[i][0];
            nxt.y = top.y + walk[i][1];
            if (vis[nxt.x][nxt.y][x ^ 1]) return true;
            if (judge(nxt, x)) {
                que[x].push(nxt);
                vis[nxt.x][nxt.y][x] = 1;
            }
        }
    }
    return false;
}

5）打代码

  1. 首先，输入我们的地图，留下外面的边框，用于减少特判。
  2. 然后就开始算步数了，看上面就好啦。
  3. 下面全代码~

AC代码 

#include <iostream>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e3 + 7;
struct Node {
    int x, y;
};
int n, m;//行列数量
int mp[MAX][MAX], vis[MAX][MAX][2];//mp为1的位置表示可走，vis为1表示走过（两个人的）
int walk[8][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, 
{ 1, 1 }, { -1, 1 }, { 1, -1 }, { -1, -1 } };//方向
queue<Node> que[2];//两个人的队列
//全局变量区

int calc();
bool judge(Node x, int res);
bool bfs(int x);
//函数预定义区

int main() {
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            char ch; cin >> ch;
            if (ch != '#') {
                mp[i][j] = 1;
                if (ch == 'C') {
                    que[0].push(Node{ i, j });
                    vis[i][j][0] = 1;
                }
                else if (ch == 'D') {
                    que[1].push(Node{ i, j });
                    vis[i][j][1] = 1;
                }
            }
        }
    int ans = calc();
    if (ans == -1) cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        cout << ans << endl;
    }
    return 0;
}
int calc() {
    int step = 1;
    while (!que[0].empty() || !que[1].empty()) {
        if (bfs(0)) return step;
        //a走一次
        if (bfs(1)) return step;
        if (bfs(1)) return step;
        //b走两次
        //判别成功表示相遇了
        step++;
    }
    return -1;
}
bool judge(Node x, int res) {
    if (!mp[x.x][x.y]) return false;
    if (vis[x.x][x.y][res]) return false;
    return true;
}
bool bfs(int x) {
    int T = que[x].size();//消耗掉原来的步数
    while (T--) {
        Node top = que[x].front(); que[x].pop();
        for (int i = 0; i < 8 - 4 * x; i++) {
            Node nxt;
            nxt.x = top.x + walk[i][0];
            nxt.y = top.y + walk[i][1];
            if (vis[nxt.x][nxt.y][x ^ 1]) return true;
            if (judge(nxt, x)) {
                que[x].push(nxt);
                vis[nxt.x][nxt.y][x] = 1;
            }
        }
    }
    return false;
}
//函数区