DDOSvoid's Blog

CF 1749E Cactus Wall

发表于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/contest/1749/problem/E

简要题意：给定一个四连通网格图，其中有一些点是障碍，需要添加最小的障碍使得不存在一条从第一行出发到达最后一行的路径，需要保证任意两个障碍不相邻

$n\times m\le 2\times 10^5$

Solution

容易发现相当于找一条从第一列到最后一列只走障碍点，且连通性为八连通减掉四连通的最短路

对于障碍点不能四连通相邻的限制我们只需要将与障碍点四连通的点视为不可走的点，障碍点视为 $0$ 边，非障碍点视为 $1$ 边，跑 $01~bfs$ 即可

时间复杂度 $O(n\times m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <deque>
#include <vector>
#include <tuple>
#define maxn 200010
#define ll long long
using namespace std;

int n, m; 
char s[maxn];
vector<int> g[maxn];
vector<int> dis[maxn], vis[maxn];
vector<pair<int, int>> pre[maxn];

tuple<int, int, int> bfs() {
    for (int i = 1; i <= n; ++i) {
        dis[i].clear(), dis[i].resize(m + 1);
        vis[i].clear(), vis[i].resize(m + 1);
        pre[i].clear(), pre[i].resize(m + 1); 
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) vis[i][j] = 0; 
    deque<pair<int, int>> Q;
    for (int i = 1; i <= n; ++i) {
        if (g[i][1] == -1) continue; vis[i][1] = 1;
        if (g[i][1]) Q.push_front({ i, 1 }), dis[i][1] = 0;
        else Q.push_back({ i, 1 }), dis[i][1] = 1; 
    } int dx[] = { 1, 1, -1, -1 }, dy[] = { 1, -1, 1, -1 };
    while (!Q.empty()) {
        auto [i, j] = Q.front(); Q.pop_front();
        if (j == m) return make_tuple(i, j, dis[i][j]);
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k], y = j + dy[k];
            if (x < 1 || x > n || y < 1 || y > m || g[x][y] == -1 || vis[x][y]) continue;
            vis[x][y] = 1; pre[x][y] = make_pair(i, j);
            if (g[x][y]) Q.push_front({ x, y }), dis[x][y] = dis[i][j];
            else Q.push_back({ x, y }), dis[x][y] = dis[i][j] + 1; 
        }
    } return make_tuple(0, 0, -1);
}

void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        g[i].clear(), g[i].resize(m + 1);
        cin >> s + 1; 
        for (int j = 1; j <= m; ++j) g[i][j] = s[j] == '#';
    } int dx[] = { 0, 0, -1, 1 }, dy[] = { 1, -1, 0, 0 };
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (!g[i][j] || g[i][j] == -1) continue;
            for (int k = 0; k < 4; ++k) {
                int x = i + dx[k], y = j + dy[k];
                if (x < 1 || x > n || y < 1 || y > m) continue;
                g[x][y] = -1;
            }
        }
    auto [x, y, ans] = bfs();
    if (ans == -1) return cout << "NO" << "\n", void();
    cout << "YES" << "\n";
    while (x && y) {
        g[x][y] = 1;
        tie(x, y) = pre[x][y];
    }
    for (int i = 1; i <= n; ++i, cout << "\n")
        for (int j = 1; j <= m; ++j) cout << (g[i][j] == 1 ? '#' : '.');
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}