简单题不简单：AtCoder ABC157 B题Bingo的二维数组模拟与复盘

有经验的刷题人通常会有一种感觉：越是放在 ABC 前两题的“简单题”，越容易在细节上翻车。2021年10月29日我重刷 AtCoder Beginner Contest 157 的 B 题 Bingo 时，又一次验证了这句话。Bingo 这道题从模型上看就是一个三行三列的标记游戏，难度不高，但它同时涉及二维数组的读入、条件标记、八条线的枚举，以及 AtCoder 严格的大小写输出要求。对刚接触竞赛编程的新手来说，这是一道非常合适的“综合小题”；对老手来说，复盘这道题也能提醒自己：别把简单题想简单。

我之所以单独把 ABC157——B - Bingo 拎出来写一篇，不是因为它难，而是因为它“麻雀虽小，五脏俱全”。如果你能完全靠自己的思路一次性通过这道题，说明你对数组下标、布尔状态和分支判断已经建立了不错的直觉；如果你在某个隐蔽角落卡住了，这篇文章正好可以把那些坑一个个摊开。

1. 为什么一道“看完就会写”的Bingo题还值得复盘

1.1 先把题目场景还原一遍

Bingo 游戏大家都听过。你手里有一张卡片，主持人在台上喊数字，如果你的卡片上有这个数字，就给这个格子做个记号。当卡片上出现了一整行、一整列或者一条对角线都被标记时，你就可以喊一句“Bingo”，宣告胜利。

AtCoder ABC157 的 B 题，做的事情就是把这个过程抽象成一道编程题。

输入会给你一个 3x3 的网格，里面每个格子放着一个整数。接下来输入一个整数 N，然后输入 N 个整数，表示主持人喊出的数字。每当喊出的数字和网格中某个位置上的数字相等时，那个位置就算是“被打上标记”。最终，你需要判断这张 3x3 的卡片上是否已经出现了一整行、一整列或者一条对角线上的三个格子全部被标记。

如果存在这样的直线，输出Yes，否则输出No。

题目最友好的地方在于，3x3 是固定的。这意味着不存在读入边长的问题，也不需要做动态二维数组的分配。也就是说，这道题没有复杂的算法，所有的难点都集中在“你能否完整地处理标记和判断”。

N 的最大值只有 10，网格也只有 9 个格子，所以即便是最粗糙的暴力写法，也只需要几十次比较。换句话说，这道题完全不需要优化，也不需要数据结构，考察的就只是你打代码的基本功。

1.2 拿到题目后，我习惯先拆成四个动作

我刷题有一个习惯：不管题目多简单，先不急着写代码，而是在草稿纸上把“要做什么”拆成几个动作。这样能避免写着写着漏掉一步。

这道题可以拆成这样：

1. 读入 3x3 网格，存到二维数组里。
2. 读入 N 和 N 个数字，每读入一个数字，就在网格里找有没有相等的格子。
3. 如果找到相等的格子，就把那个格子对应的“标记状态”置为 true。
4. 最后检查 3 行、3 列、2 条对角线，看是否存在一条线全部被标记。

前两步是模拟，第三步是判断，思路非常直白。

这里有一个小建议：在草稿纸上把“行、列、对角线”这八条线都写出来，再去写代码。不要只在脑子里想，因为二维数组的下标非常容易看走眼。后面我会把八条线具体坐标列出来。

2. “标记格子”这一步，藏着所有后续判断的基础

2.1 最朴素的标记方式，恰恰是最稳的

标记格子听起来很简单，但新手经常犯一个错误：试图用“原始数字网格”本身来记录标记状态。比如有人会想，把被喊到的数字直接改成 0，表示这个格子已经被标记。这种方法不是不行，但后患无穷。因为题目只要求判断是否存在完整的线，并不需要记录格子原来的值；可一旦你直接把数组改成 0，万一后面有别的数字要和原数组比较，就再也比不出来了。

更清晰的思路是单独开一个二维布尔数组marked[3][3]，专门记录每个格子是否被标记。

标记过程也很直白：每读入一个数字 b，就两层循环遍历整个 3x3 网格，如果a[i][j] == b，就把marked[i][j]置为 true。

有人可能会问：这样不会太暴力吗？每次遍历 9 个格子，N 最大 10，一共也就 90 次比较。这个开销小到完全不需要考虑。

为什么我不推荐一上来就建哈希表？因为题目中的数字范围不大，而且输入规模非常小，哈希表带来的常数开销反而比朴素遍历更大。更关键的是，如果网格里出现了两个相同的数字，如果你用简单的“数字到坐标”映射来存，后一个位置会把前一个位置覆盖。到时候喊出这个数字，你只能标记到最后一个匹配位置，前面的那个格子就会漏掉。

所以，在这个数据规模下，最朴素的双层循环比较才是真正的“最优解”。它不是性能最优，而是正确性最稳。

2.2 标记阶段的代码与初始化细节

下面先用 Python 写一个标记阶段的片段：

a = [list(map(int, input().split())) for _ in range(3)] n = int(input()) marked = [[False] * 3 for _ in range(3)] for _ in range(n): b = int(input()) for i in range(3): for j in range(3): if a[i][j] == b: marked[i][j] = True

如果换成 C++，唯一需要特别注意的是数组初始化：

int a[3][3]; bool marked[3][3] = {};

bool marked[3][3] = {};会把所有元素初始化为 false。如果你只写bool marked[3][3];，那么数组里可能是一些随机值，后面判断时会出现“明明没有标记却显示为 true”的诡异情况。这个坑是用 C++ 刷题时特别值得警惕的。

标记阶段结束后，marked数组就代表了一张“被打过孔”的卡片。接下来的问题就变成了：如何判断卡片上有没有一条完整的线。

3. 八条线的判断：从“手写枚举”到“循环统一”

3.1 把八条线用坐标表格列出来

3x3 的卡片上一共有八条可能的获胜线：三条行线、三条列线、两条对角线。把这八条线的坐标列出来，代码就会写得非常有底气。

这张表就是整道题的核心。

判断是否存在一条完整线，本质就是把上面八条线“翻译”成代码里的条件表达式。

最直接的方法是手写八个 if。这样写比较啰嗦，但不容易出错。比如判断主对角线，只需要检查：

marked[0][0] && marked[1][1] && marked[2][2]

判断副对角线则是：

marked[0][2] && marked[1][1] && marked[2][0]

这种写法的好处是清晰，每一行对应现实中的一条线，想漏都难。坏处是代码有些重复，尤其是判断三条行线和三条列线时，可以用循环压缩。

3.2 两种判断写法的对比

我推荐的写法是“循环判断行和列，单独判断对角线”。

行线和列线具有很强的规律性。三行分别对应i = 0, 1, 2；三列分别对应j = 0, 1, 2。所以可以用一个循环同时检查行和列：

for (int i = 0; i < 3; i++) { if (marked[i][0] && marked[i][1] && marked[i][2]) { cout << "Yes\n"; return 0; } if (marked[0][i] && marked[1][i] && marked[2][i]) { cout << "Yes\n"; return 0; } }

这段代码里，第一个 if 检查的是第 i 行的三个格子，第二个 if 检查的是第 i 列的三个格子。

两条对角线不具备这种循环结构，单独写两个 if 就好。

也有一种更统一的做法：把八条线的坐标预先存到一个数组里，再统一遍历。比如：

int lines[8][3][2] = { {{0,0},{0,1},{0,2}}, {{1,0},{1,1},{1,2}}, {{2,0},{2,1},{2,2}}, {{0,0},{1,0},{2,0}}, {{0,1},{1,1},{2,1}}, {{0,2},{1,2},{2,2}}, {{0,0},{1,1},{2,2}}, {{0,2},{1,1},{2,0}} };

然后用一个双重循环去遍历每条线、每个点。这样做的好处是代码更“通用”，如果以后要扩展到 N x N 网格，只需要修改 lines 的生成方式即可。

但话说回来，本题只有八条线，数据规模又极小，选择哪种写法的唯一标准是“你自己看得懂”。不要在比赛里追求代码的优雅而放弃熟练度。

3.3 完整参考代码

下面给出一份完整的 C++ 参考代码：

#include <bits/stdc++.h> using namespace std; int main() { int a[3][3]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cin >> a[i][j]; } } int n; cin >> n; bool marked[3][3] = {}; for (int k = 0; k < n; k++) { int b; cin >> b; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (a[i][j] == b) { marked[i][j] = true; } } } } for (int i = 0; i < 3; i++) { if (marked[i][0] && marked[i][1] && marked[i][2]) { cout << "Yes\n"; return 0; } if (marked[0][i] && marked[1][i] && marked[2][i]) { cout << "Yes\n"; return 0; } } if (marked[0][0] && marked[1][1] && marked[2][2]) { cout << "Yes\n"; return 0; } if (marked[0][2] && marked[1][1] && marked[2][0]) { cout << "Yes\n"; return 0; } cout << "No\n"; return 0; }

Python 版本可以这样写：

a = [list(map(int, input().split())) for _ in range(3)] n = int(input()) marked = [[False] * 3 for _ in range(3)] for _ in range(n): b = int(input()) for i in range(3): for j in range(3): if a[i][j] == b: marked[i][j] = True ok = False for i in range(3): if all(marked[i][j] for j in range(3)): ok = True if all(marked[j][i] for j in range(3)): ok = True if all(marked[i][i] for i in range(3)): ok = True if all(marked[i][2 - i] for i in range(3)): ok = True print("Yes" if ok else "No")

这段 Python 代码里用到了all()，它接收一个可迭代对象，只有当所有元素都为 true 时才返回 true。用在这里非常合适。

复杂度方面，标记阶段是 O(9N)，判断阶段是 O(8)，空间是 O(9) 的布尔矩阵。因为 N 最大只有 10，实际执行的比较次数不超过 100 次，运行时间几乎为 0。

4. 我在提交时踩过的坑，以及如何一次通过

4.1 输出不是“YES”，而是“Yes”

这是 AtCoder 新手最容易踩的坑之一。AtCoder 的输出判定是严格区分大小写的，题目要求输出Yes，就必须是Yes。如果你习惯性地写成了全大写的YES，或者写成了yes，哪怕你的逻辑完全正确，最后也一定是 WA。

我见过不少参赛者在简单题上翻车，原因不是算法不会，而是输出格式差了一个字母。

最稳妥的做法是：从题目描述里把输出格式抄下来，或者从样例输出里复制。不要凭感觉写。

4.2 布尔数组忘了初始化，开场就翻车

如果你用 C++ 写这道题，声明bool marked[3][3];之后不做任何初始化，那么这个数组里存的值是未定义的。局部变量的初始值可能是 0，也可能是任意非 0 值。

这意味着某个格子明明没有被标记，但marked[i][j]可能为 true，最后可能错误地输出Yes，也可能恰好输出No，但已经不符合逻辑。

解决办法就是在声明时写= {}：

bool marked[3][3] = {};

这个语法会把整个数组的所有元素都初始化为 false。你也可以用memset(marked, 0, sizeof(marked));，但更推荐前者，简洁且不容易写错。

4.3 用哈希表记录数字位置时，可能被重复值坑到

这道题的数据范围很小，所以我前面一直推荐直接遍历比较。但我在交流群里看到过不少同学会选择“建立数字到坐标的映射”，也就是：

map<int, pair<int,int>> pos; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { pos[a[i][j]] = {i, j}; } }

这段代码初看没问题，但如果 3x3 网格里出现了两个相同的数字，pos只会保留最后一次出现的坐标。等主持人喊出这个数字时，另一个相同数字所在的格子就不会被标记。

原题并没有要求我们利用数字的唯一性来做任何优化，所以直接遍历是最安全的。如果你喜欢用哈希表，至少也要用map<int, vector<pair<int,int>>>，把同一个数字出现的所有坐标都存下来。可这样反而把事情变复杂了，完全没有必要。

4.4 提前输出后忘了 return，代码会“说话”

在 C++ 代码中，如果你在判断出行线存在后直接cout << "Yes\n";，却没有写return 0;，程序不会停下来，而是会继续往下执行。如果后面的某个条件也成立，可能会再输出一次Yes；如果后面的条件不成立，最后可能输出一个No。

这样输出结果会变成两行，第一行Yes，第二行No。AtCoder 的判定器拿到多行输出后，大概率判你 WA。

所以一旦找到一条获胜线，务必在输出后立即终止程序。上面给出的 C++ 代码中，每个cout << "Yes\n";后面都跟了return 0;，就是为了避免这个问题。

5. 从3x3的Bingo出发，还能延展成哪些题型

5.1 扩大到 N x N 网格的判定

既然 3x3 的 Bingo 会判断八条线，那么如果题目变成 N x N 网格，判断方式其实也没有本质变化。

行和列的判断可以这样写：

for (int i = 0; i < n; i++) { bool row_ok = true; bool col_ok = true; for (int j = 0; j < n; j++) { if (!marked[i][j]) row_ok = false; if (!marked[j][i]) col_ok = false; } if (row_ok || col_ok) return true; }

对角线判断则要检查两条：

bool diag1 = true, diag2 = true; for (int i = 0; i < n; i++) { if (!marked[i][i]) diag1 = false; if (!marked[i][n - 1 - i]) diag2 = false; } if (diag1 || diag2) return true;

这种扩展在题目中很常见。如果你能把 3x3 版本吃透，N x N 版本只是多加一个循环而已。

5.2 用位运算状态压缩写出更紧凑的判断

再往后走一步，如果网格始终是 3x3，我们可以用 9 个二进制位表示标记状态。每一个格子对应一位，该位为 1 表示被标记，为 0 表示未被标记。

假设格子的编号从左到右、从上到下依次是 0 到 8，那么第 i 行第 j 列的格子对应的二进制位就是：

1 << (i * 3 + j)

每次标记格子时，做一次按位或运算：

state |= 1 << (i * 3 + j);

然后预先把八条线的掩码存下来：

int win[8] = { 0b111000000, // 第 0 行 0b000111000, // 第 1 行 0b000000111, // 第 2 行 0b100100100, // 第 0 列 0b010010010, // 第 1 列 0b001001001, // 第 2 列 0b100010001, // 主对角线 0b001010100 // 副对角线 };

判断是否存在 Bingo 的思路是：

for (int i = 0; i < 8; i++) { if ((state & win[i]) == win[i]) { cout << "Yes\n"; return 0; } }

(state & win[i]) == win[i]的含义是：win[i] 中为 1 的那些位，在 state 中必须全部为 1。这和逐个判断marked数组是等价的，但代码更紧凑。

这种位运算技巧在很多状态压缩题目里都会用到。它不需要二维数组，只用两个 int 型变量就能搞定，是很好的思维训练。

5.3 再进一步：任意方向K连子判定

如果题目从“整行整列”变成“只要在任意方向上连续 K 个就算赢”，那就更像五子棋或者井字棋的变种。

这种情况下，固定枚举所有行、列、对角线就不够用了。常见做法是枚举每个格子作为起点，然后向上下左右、四个斜方向一共八个方向扩展，统计连续被标记的格子数量。

方向可以预先用方向数组表示：

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

然后从一个起点出发，沿着某个方向走 K 步，看看每一步是否都在棋盘内且被标记。

这样做的好处是通用，坏处是常数比较大，但通常数据范围不大时也够用。如果你掌握了从“枚举固定线”到“方向扩展”的转变，你对搜索题的理解也会上一个台阶。

6. 重刷这道简单题，我最大的三个收获

第一，简单题的答案往往不是“用高级技巧”，而是“把基本动作做对”。ABC157 的 B - Bingo 不需要任何优化，也不需要高级数据结构。只要二维数组读入正确、标记正确、八条线枚举完整，就能通过。很多时候我们 WA，不是因为不会难题，而是因为在最简单的步骤上手滑了。

第二，草稿纸上的表格比脑子里的想象可靠。我在写这道题时，把八条线的坐标列成表格，然后照着表格写判断条件。这个过程看起来很笨，但能有效减少下标错误。

第三，一次通过的秘诀就是提前想好所有边界。每次提交前，我会在样例之外再构造几个用例。比如全部标记、没有任何标记、只差一个格子就 Bingo、副对角线恰好成立。这组用例跑下来，基本可以覆盖所有分支。

2021年10月29日那天，我用最朴素的写法把这道题一次 AC。现在回头看，它仍然是我愿意推荐给新手的题目之一：不靠奇技淫巧，纯粹考察你能不能把一句话描述的问题，变成一段不会出错的代码。