牛客小白月赛13 G（双向搜索）

AC通道

两边同步搜，一步里面A走一次B走两次，遇到对方走过的地方就得到了答案。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1001;

const int tx[] = {-1, 1, 0, 0, -1, -1, 1, 1};

const int ty[] = {0, 0, -1, 1, -1, 1, -1, 1};

int N, M, Ax, Ay, Bx, By;

bool vis[2][maxn][maxn];

char maze[maxn][maxn];

queue<pair<int, int>> Q[2];

bool bfs(int t) {

    int control = Q[t].size();

    while (control--) {

        auto tmp = Q[t].front(); Q[t].pop();

        for (int i = 0; i < 8 - 4 * t; i++) {

            int x = tmp.first + tx[i];

            int y = tmp.second + ty[i];

            if (x < 0 || x >= N || y < 0 || y >= M || maze[x][y] == '#')

                continue;

            if (vis[1 - t][x][y])    return 1;

            if (!vis[t][x][y])    Q[t].push({x, y}), vis[t][x][y] = 1;

        }

    }

    return 0;

}

int solve() {

    Q[0].push({Ax, Ay});

    Q[1].push({Bx, By});

    vis[0][Ax][Ay] = 1;

    vis[1][Bx][By] = 1;

    int step = 0;

    while (!Q[0].empty() || !Q[1].empty()) {

        step++;

        if (bfs(0))    return step;

        if (bfs(1))    return step;

        if (bfs(1))    return step;

    }

    return -1;

}

int main() {

    scanf("%d %d", &N, &M);

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < M; j++) {

            getchar();

            maze[i][j] = getchar();

            if (maze[i][j] == 'C')    Ax = i, Ay = j;

            if (maze[i][j] == 'D')    Bx = i, By = j;

        }

    }

    int ans = solve();

    if (ans >= 0)    printf("YES\n%d\n", ans);

    else    puts("NO");

    return 0;

}

巴特西

牛客小白月赛13 G（双向搜索）

最新文章

热门文章