解题思路

给定一个 矩阵表示迷宫，其中 C 表示小A的位置，D 表示小B的的位置，# 表示不可通过的障碍，. 表示可正常通过的位置。
小A每次可以移动一个位置，移动的方向是上下左右左上左下右上右下 8 个方向；
小B每次可以移动两次位置，移动的方向是上下左右 4 个方向。
请问他们是否能够相遇，如果能，那么最早什么时候能够找到对方。

广度优先搜索：
每单位时间对小A使用一次 ，对小B使用两次 ，如果小A或小B走到了对方走过的位置，则表示相遇。

C++代码

#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;

int N, M;
int d[8][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};
queue<pair<int,int>> qa, qb;
int va[1001][1001];
int vb[1001][1001];
bool bfs1(vector<vector<char>>& ground){
    int k = qa.size();
    while(k){
        int x1 = qa.front().first;
        int y1 = qa.front().second;
        qa.pop();
        for(int i=0; i<8; ++i){
            int x = x1 + d[i][0];
            int y = y1 + d[i][1];
            if(x>=0 && x<N && y>=0 && y<M && ground[x][y]!='#' && va[x][y]==0){
                qa.push(make_pair(x,y));
                va[x][y] = 1;
                if(vb[x][y])
                    return true;
            }
        }
        --k;
    }
    return false;
}

bool bfs2(vector<vector<char>>& ground){
    int k = qb.size();
    while(k){
        int x2 = qb.front().first;
        int y2 = qb.front().second;
        qb.pop();
        for(int i=0; i<4; ++i){
            int x = x2 + d[i][0];
            int y = y2 + d[i][1];
            if(x>=0 && x<N && y>=0 && y<M && ground[x][y]!='#' && vb[x][y]==0){
                qb.push(make_pair(x,y));
                vb[x][y] = 1;
                if(va[x][y])
                    return true;
            }
        }
        --k;
    }
    return false;
}

int main(){
    cin >> N >> M;
    memset(va, 0, 1001);
    memset(vb, 0, 1001);
    vector<vector<char>> ground(N, vector<char>(M));
    int ax, ay, bx, by;
    for(int i=0; i<N; ++i){
        for(int j=0; j<M; ++j){
            cin >> ground[i][j];
            if(ground[i][j] == 'C'){
                ax = i;
                ay = j;
            }
            if(ground[i][j] == 'D'){
                bx = i;
                by = j;
            }
        }
    }
    va[ax][ay] = 1;
    vb[bx][by] = 1;
    qa.push(make_pair(ax,ay));
    qb.push(make_pair(bx,by));
    int cnt = 1;
    bool meet = false;
    while(!qa.empty() || !qb.empty()){
        if(bfs1(ground)){
            meet = true;
            break;
        }
        if(bfs2(ground)){
            meet = true;
            break;
        }
        if(bfs2(ground)){
            meet = true;
            break;
        }
        ++cnt;
    }
    if(meet)
        cout << "YES" << endl << cnt << endl;
    else
        cout << "NO" << endl;
    return 0;
}