[CF1365D] Solve The Maze - 构造,BFS

Description

给出一个 \(n\) 行 \(m\) 列的网格，每个格子上有四种情况，. 表示这个格子是空地，# 表示这个格子是墙，G 表示这个格子是好人，B 表示这个格子是坏人，G，B格子都可以认为是空地，你需要判断能否 . 格子上放任意数量的墙，保证所有好人可以通过在空地间移动到达点 \((n,m)\) 而所有坏人都不行。

Solution

对坏人的上下左右四个位置建墙，然后判断所有好人与 \((n,m)\) 是否连通

考虑正确性：如果一个位置建墙是错误的，也就是这个位置建墙导致了好人无法走到，但是这个位置不建立墙也可*坏人。这时，这个好人必然会经过这个位置，那么坏人可以一直跟着这个好人走到终点，矛盾。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 105;

char a[N][N];
int vis[N][N];

const int di[4] = {0, 0, -1, 1}, dj[4] = {1, -1, 0, 0};

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            vis[i][j] = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i] + 1;

    vector<pair<int, int>> vec, vecb;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 'B')
            {
                vecb.push_back({i, j});
            }
            else if (a[i][j] == 'G')
            {
                vec.push_back({i, j});
            }
        }
    }

    for (auto [x, y] : vecb)
    {
        int i = x, j = y;
        for (int dir = 0; dir < 4; dir++)
        {
            int ni = i + di[dir], nj = j + dj[dir];
            if (ni > 0 && nj > 0 && ni <= n && nj <= m)
            {
                a[ni][nj] = '#';
            }
        }
    }

    // for (int i = 1; i <= n; i++)
    // {
    //     cerr << " " << a[i] + 1 << endl;
    // }
    // cerr << endl;

    queue<pair<int, int>> que;
    int i = n, j = m;
    if (a[i][j] != 'B' && a[i][j] != '#')
    {
        vis[n][m] = 1;
        que.push({n, m});
    }
    while (que.size())
    {
        auto [i, j] = que.front();
        que.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int ni = i + di[dir], nj = j + dj[dir];

            if (ni > 0 && nj > 0 && ni <= n && nj <= m)
            {
                if (a[ni][nj] == '#')
                    continue;
                if (!vis[ni][nj])
                    que.push({ni, nj});
                vis[ni][nj] = 1;
            }
        }
    }

    for (auto [i, j] : vec)
    {
        if (vis[i][j] == 0 || a[i][j] == '#')
        {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--)
        solve();
}