消除类游戏

形式化题目

给定一个 $n \times m$ 的棋盘，每个格子有一个颜色（ $1 \sim 9$ ）。一次消除操作中，所有满足“所在行或所在列有连续至少 3 个相同颜色”的格子被同时清除，输出清除后的棋盘（被清除的格子输出 0）。

思路

“同时消除”是本题的核心约束：如果一边扫描一边修改棋盘，先消除的位置会破坏后面行、列的判断。因此分两步：

标记：用 removed 数组记录哪些格子要被消除，而不改变 board 本身。
输出：全部标记完成后，被标记的格子输出 0，其余输出原颜色。

标记方法

对每一行扫描极长相同段：

用两个指针 left、right 找出连续同色区间；
若区间长度 $\geqslant 3$ ，把区间内所有格子标记为消除。

对每一列重复同样的扫描。一个格子可能同时被行、列标记，最终统一置零，天然满足“同时被消除”。

代码

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:59
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n, m;
int board[MAXN][MAXN];    // 棋盘颜色
int removed[MAXN][MAXN];  // removed[i][j]=1 表示该格被消除

// 扫描第 row 行，把连续三个及以上同色的格子标记为消除。
void mark_row(int row) {
    for (int left = 0; left < m;) {
        int right = left + 1;
        while (right < m && board[row][right] == board[row][left]) right++;
        if (right - left >= 3) {
            for (int j = left; j < right; j++) removed[row][j] = 1;
        }
        left = right;
    }
}

// 扫描第 column 列，把连续三个及以上同色的格子标记为消除。
void mark_column(int column) {
    for (int top = 0; top < n;) {
        int bottom = top + 1;
        while (bottom < n && board[bottom][column] == board[top][column]) bottom++;
        if (bottom - top >= 3) {
            for (int i = top; i < bottom; i++) removed[i][column] = 1;
        }
        top = bottom;
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> board[i][j];
    }

    // 先全部标记再输出：某格同时满足行、列条件也只消除一次。
    for (int i = 0; i < n; i++) mark_row(i);
    for (int j = 0; j < m; j++) mark_column(j);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j > 0) cout << ' ';
            cout << (removed[i][j] ? 0 : board[i][j]);
        }
        cout << '\n';
    }
    return 0;
}

复杂度

时间：每行、每列各扫描一次， $O(nm)$ 。
空间：board 与 removed 两个数组， $O(nm)$ 。

总结

“同时消除”要求检测与修改分离：先完整标记、后统一输出。两指针扫描极长相同段是这类连续段判定题的基础技巧，与“求连续相同子段长度”是同一套想法。

目录

形式化题目

思路

标记方法

代码

复杂度

总结