2D Conveyor Belt

题意

有一个 $N\times N$ 网格。每个格子要么是固定方向传送带 $L/R/U/D$ ，要么还是 ?。

初始所有格子都是 ?。接下来每天会把一个 ? 改成固定方向。每天结束后，可以把剩余所有 ? 任意补成方向，要求最小化不可用格子数量。

不可用格子表示：从这个格子放入物品后，物品永远不会离开网格。

思路

先看朴素做法：每次更新后，重新计算整张网格里哪些格子能离开网格。

cpp

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:48
 * update_at: 2026-07-11 20:54
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, q;
int dir_grid[MAXN][MAXN]; // -1 表示 ?，0/1/2/3 分别表示 L/R/U/D。
bool good[MAXN][MAXN];
int cur_good;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

queue<pair<int, int> > que;

int get_dir(char ch) {
    if (ch == 'L') return 0;
    if (ch == 'R') return 1;
    if (ch == 'U') return 2;
    return 3;
}

bool inside(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

bool can_be_good(int x, int y) {
    if (!inside(x, y)) return false;

    for (int d = 0; d < 4; d++) {
        if (dir_grid[x][y] != -1 && dir_grid[x][y] != d) continue;

        int nx = x + dx[d];
        int ny = y + dy[d];
        if (!inside(nx, ny) || good[nx][ny]) {
            return true;
        }
    }
    return false;
}

void try_add(int x, int y) {
    if (!inside(x, y)) return;
    if (good[x][y]) return;
    if (!can_be_good(x, y)) return;

    good[x][y] = true;
    cur_good++;
    que.push(make_pair(x, y));

    while (!que.empty()) {
        int now_x = que.front().first;
        int now_y = que.front().second;
        que.pop();

        for (int d = 0; d < 4; d++) {
            int nx = now_x + dx[d];
            int ny = now_y + dy[d];
            if (!inside(nx, ny)) continue;
            if (good[nx][ny]) continue;
            if (!can_be_good(nx, ny)) continue;

            good[nx][ny] = true;
            cur_good++;
            que.push(make_pair(nx, ny));
        }
    }
}

int calc_bad() {
    cur_good = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            good[i][j] = false;
        }
    }

    // 暴力做法：每次更新后，从头重新扩展所有 good 格子。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            try_add(i, j);
        }
    }

    return n * n - cur_good;
}

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

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dir_grid[i][j] = -1;
        }
    }

    for (int i = 1; i <= q; i++) {
        int r, c;
        char ch;
        cin >> r >> c >> ch;
        dir_grid[r][c] = get_dir(ch);
        cout << calc_bad() << '\n';
    }

    return 0;
}

这个暴力的关键是定义 good：如果从一个格子出发可以离开网格，那么它就是 good。

固定某一天的网格后，一个格子变成 good 的条件如下：

格子类型	什么时候是 `good`
`?`	可以选择某个方向直接出界，或者走向相邻的 `good` 格子
固定方向	固定方向直接出界，或者固定方向走向相邻的 `good` 格子

所以可以从已经能出界的格子开始，向反方向 BFS，把所有“能走到 good 格子”的格子也标记为 good。

朴素做法每次更新都重新 BFS，复杂度是 $O(QN^2)$ ，过不了完整数据。

关键观察是：正序加入传送带会让可选方向变少，good 集合可能变小；但倒序撤销传送带会让可选方向变多，good 集合只会变大。

于是满分做法如下：

读入所有更新，先构造最终网格。
在最终网格上计算一次 good 集合。
从第 Q 天倒着处理到第 1 天。
在撤销第 day 天的传送带之前，当前状态正好对应正序第 day 天结束后的状态，记录答案。
把这个格子改回 ?，如果它因此能变成 good，就用 BFS 继续扩展邻居。

每个格子最多从非 good 变成 good 一次，所以总扩展次数是线性的。

实现时用 try_add(x,y) 表示：如果 (x,y) 当前可以成为 good，就入队并继续检查它的四个邻居。官方解析里使用递归 DFS，这里改成队列 BFS，避免 $N=1000$ 时递归层数太深。

代码

cpp

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 20:48
 * update_at: 2026-07-11 20:54
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXQ = 200005;

int n, q;
int dir_grid[MAXN][MAXN]; // -1 表示 ?，0/1/2/3 分别表示 L/R/U/D。
bool good[MAXN][MAXN];    // good[i][j] 表示从这个格子出发可以离开网格。
int rr[MAXQ], cc[MAXQ], tt[MAXQ];
int ans[MAXQ];
int cur_good;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

queue<pair<int, int> > que;

int get_dir(char ch) {
    if (ch == 'L') return 0;
    if (ch == 'R') return 1;
    if (ch == 'U') return 2;
    return 3;
}

bool inside(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

// 判断当前状态下，格子 (x,y) 是否已经能成为 good。
bool can_be_good(int x, int y) {
    if (!inside(x, y)) return false;

    for (int d = 0; d < 4; d++) {
        if (dir_grid[x][y] != -1 && dir_grid[x][y] != d) continue;

        int nx = x + dx[d];
        int ny = y + dy[d];
        if (!inside(nx, ny) || good[nx][ny]) {
            return true;
        }
    }
    return false;
}

// 如果 (x,y) 可以变成 good，就把它加入队列并向反方向扩展。
void try_add(int x, int y) {
    if (!inside(x, y)) return;
    if (good[x][y]) return;
    if (!can_be_good(x, y)) return;

    good[x][y] = true;
    cur_good++;
    que.push(make_pair(x, y));

    while (!que.empty()) {
        int now_x = que.front().first;
        int now_y = que.front().second;
        que.pop();

        for (int d = 0; d < 4; d++) {
            int nx = now_x + dx[d];
            int ny = now_y + dy[d];
            if (!inside(nx, ny)) continue;
            if (good[nx][ny]) continue;
            if (!can_be_good(nx, ny)) continue;

            good[nx][ny] = true;
            cur_good++;
            que.push(make_pair(nx, ny));
        }
    }
}

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

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dir_grid[i][j] = -1;
        }
    }

    for (int i = 1; i <= q; i++) {
        char ch;
        cin >> rr[i] >> cc[i] >> ch;
        tt[i] = get_dir(ch);
        dir_grid[rr[i]][cc[i]] = tt[i];
    }

    // 先在最终状态下找出所有能离开网格的格子。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            try_add(i, j);
        }
    }

    // 倒着撤销传送带。撤销只会让 good 集合变大，不会让它变小。
    for (int day = q; day >= 1; day--) {
        ans[day] = n * n - cur_good;
        dir_grid[rr[day]][cc[day]] = -1;
        try_add(rr[day], cc[day]);
    }

    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

复杂度

最终状态初始化需要 $O(N^2)$ 。

倒序过程中，每个格子最多入队一次，每次检查四个方向，总复杂度为 $O(N^2+Q)$ 。

空间复杂度为 $O(N^2+Q)$ 。

总结

这题的核心是把“不可用”反过来看成“能不能离开网格”。

固定网格时，good 可以用反向 BFS 求出。动态更新时，正序不好维护，但倒序撤销会让 good 集合单调扩大，因此每个格子只处理一次。

目录

题意

思路

代码

复杂度

总结