华为OD真题“竖直四子棋”详解：从算法实现到工程避坑

1. 项目概述：从一道华为OD真题看编程实战

最近在技术社区和求职圈里，华为OD的机试真题热度一直居高不下，尤其是C卷的题目，常常成为大家讨论和模拟练习的重点。我注意到一道名为“竖直四子棋”的题目，标称是200分且100%通过率的真题。这立刻引起了我的兴趣，因为“四子棋”本身是一个经典的博弈类问题，而“竖直”这个限定词又暗示了规则上可能有的变化。对于正在准备类似机考，或者单纯想提升自己C/C++算法与工程实现能力的朋友来说，深入剖析这道题，远不止是得到一份“能AC的代码”那么简单。它更像是一个完整的项目缩影，涵盖了问题理解、逻辑抽象、数据结构设计、核心算法实现、边界处理以及代码健壮性测试的全流程。今天，我就结合自己多年的开发经验，把这道题掰开揉碎了讲，不仅给出思路和代码，更重点分享在实现过程中那些容易踩坑的细节和调试心得，希望能帮你真正吃透这一类问题。

2. 问题深度解析与核心逻辑建模

拿到任何算法题，第一步也是最关键的一步，就是彻底理解题意。题目描述通常是简洁的，但魔鬼藏在细节里。

2.1 “竖直四子棋”规则还原与抽象

根据常见的“四子棋”（Connect Four）和“竖直”这个修饰语，我们可以推断出题目的核心规则。标准四子棋是在一个水平的网格中，棋子受重力下落，玩家轮流在某一列顶部放入棋子，棋子会落到该列最低的空位。获胜条件是横、竖、斜（两种对角线）方向有四个己方棋子连成一线。

那么“竖直”四子棋有何不同？我推测，这里的“竖直”可能强调了棋盘的方向性或落子规则的特异性。一种合理的解读是：棋盘是竖直放置的，即我们通常看到的棋盘旋转了90度。但这对于计算机内部的二维数组表示来说，只是坐标映射的问题，本质不变。另一种更可能、也更能增加题目复杂度的解读是：棋子不再受“重力”影响下落至最低处，而是严格放置在所选择列的“顶部”，并且后续棋子会堆叠在已有棋子之上。这听起来和标准规则一样？请注意，在标准的水平棋盘视角下，“顶部”就是第一行。但在竖直视角下，“顶部”可能对应的是数组的起始索引（如[0][col]）。关键在于，无论视角如何，落子的逻辑是固定的：在选定列col，从该列的第一个空位（可能是从上往下找，也可能是从下往上找）放入棋子。

因此，我们需要从题目描述（虽然这里未给出原文）中确认几个核心点，这在机试中至关重要：

1. 棋盘规模：行数（R）和列数（C）是多少？常见的是6行7列，但考题可能变化。
2. 落子规则：给定一个列号col（假设从0或1开始索引），棋子应放在该列的哪个位置？是找到该列中第一个为“空”的行索引。
3. 获胜判定：需要检查四个方向：水平（同一行）、垂直（同一列）、主对角线（从左上到右下）、副对角线（从右上到左下）。只要有任意方向满足连续四个相同棋子，游戏立即结束，当前落子玩家获胜。
4. 输入输出格式：输入如何给出？是一连串的落子列序列吗？输出是什么？是每一步后的棋盘状态，还是最终获胜者和步数，或者是“Draw”平局？

注意：在真实的华为OD考试中，务必仔细阅读题目说明中的每一句话、每一个示例。我见过太多人因为忽略了“棋盘满员即平局”或者“列号从1开始”这样的细节而丢分。这里我们基于最常见的情况进行建模：一个R行C列的网格，玩家1和玩家2轮流输入一个有效的列号，棋子落入该列最低的空位（假设第0行是顶部，第R-1行是底部）。如果落子后导致四子连珠，则当前玩家胜；如果棋盘下满仍未分胜负，则为平局。

2.2 数据结构设计与选择

明确了规则，接下来就要为这个游戏世界选择合适的数据容器。这直接影响到后续代码的简洁性和效率。

方案一：二维向量/数组最直观的，使用vector<vector<int>> board(R, vector<int>(C, 0))或者原生二维数组int board[R][C]。用0表示空位，1和2分别表示两位玩家的棋子。

• 优点：访问任意位置board[row][col]非常快，符合人类思维直觉，便于调试时打印棋盘。
• 缺点：在判断某一列是否已满，或者找到该列第一个空位时，需要遍历该列的所有行。在R和C不大（比如<=10）的情况下，这完全不是问题。

方案二：为每一列维护一个“高度”数组由于落子只依赖于列的状态，我们可以额外使用一个数组vector<int> colHeight(C, 0)，记录每一列当前已经有多少颗棋子（即下一个棋子的行索引）。这样，当玩家选择列c时，下一个空位的行就是colHeight[c]。落子后，执行board[colHeight[c]][c] = player; colHeight[c]++。

• 优点：将落子操作的时间复杂度从O(R)降低到O(1)，代码更精炼。
• 缺点：需要额外维护一个数组，但空间开销极小。

对于这道题，两种方案都可以。但方案二更能体现对问题特性的优化思考，这在机试中可能是加分项。我们选择方案二作为基础。

方案三：位棋盘这是一种极致的优化，用整数的每一个bit来代表棋盘上的一个位置状态。对于四子棋，由于每个点有三种状态（空、玩家1、玩家2），可能需要两个bit位图。这种方法在追求极限性能的AI对弈中常见，但对于机试和日常理解而言过于复杂，不推荐。

因此，我们的核心数据结构如下：

int rows, cols; // 棋盘行数和列数 vector<vector<int>> board; // 棋盘状态，0为空，1为玩家1，2为玩家2 vector<int> colHeight; // 每列当前高度（即该列下一个棋子应放的行索引） int currentPlayer; // 当前玩家，1或2

3. 核心算法实现与关键代码拆解

有了清晰的数据模型，我们就可以动手实现核心逻辑了。整个程序可以划分为几个清晰的模块。

3.1 初始化与棋盘状态管理

首先，我们需要根据输入初始化棋盘。假设题目输入第一行是行数R和列数C，后续是一系列落子列（假设从0开始索引）。

// 初始化棋盘 rows = R; cols = C; board.assign(rows, vector<int>(cols, 0)); // 所有位置初始化为0（空） colHeight.assign(cols, 0); // 所有列高度初始化为0 currentPlayer = 1; // 玩家1先手

一个良好的习惯是编写一个打印棋盘的函数，用于调试，这在复杂逻辑中至关重要。

void printBoard() { // 逆序打印，让最后落子的底部在控制台下方，更符合观看习惯 for (int i = rows - 1; i >= 0; --i) { for (int j = 0; j < cols; ++j) { char c; switch(board[i][j]) { case 0: c = '.'; break; case 1: c = 'X'; break; // 玩家1 case 2: c = 'O'; break; // 玩家2 default: c = '?'; } cout << c << ' '; } cout << endl; } // 打印列号，方便查看 for (int j = 0; j < cols; ++j) cout << "--"; cout << endl; for (int j = 0; j < cols; ++j) cout << j << ' '; cout << endl << endl; }

3.2 落子操作与有效性校验

这是游戏的核心驱动函数。每次落子需要：

1. 检查列号是否合法。
2. 检查该列是否已满。
3. 放置棋子。
4. 更新列高度。
5. 检查是否获胜或平局。

// 返回值：-1表示无效操作，0表示正常落子未结束，1表示玩家1胜，2表示玩家2胜，3表示平局 int dropPiece(int col) { // 1. 校验列号 if (col < 0 || col >= cols) { return -1; // 无效列 } // 2. 校验该列是否已满 if (colHeight[col] >= rows) { return -1; // 该列已满，无法落子 } // 3. 放置棋子 int row = colHeight[col]; board[row][col] = currentPlayer; // 4. 更新列高度 colHeight[col]++; // 5. 检查游戏状态 if (checkWin(row, col)) { return currentPlayer; // 当前玩家获胜 } // 检查是否平局：所有列都满了 bool isDraw = true; for (int h : colHeight) { if (h < rows) { isDraw = false; break; } } if (isDraw) { return 3; // 平局 } // 切换玩家 currentPlayer = (currentPlayer == 1) ? 2 : 1; return 0; // 游戏继续 }

3.3 获胜判定算法的优化实现

checkWin(int row, int col)函数是算法的精髓。最笨的方法是每次落子后扫描整个棋盘，但那样效率太低。正确做法是以刚落子的位置(row, col)为中心，向四个方向探测。

方向向量：

• 水平：(0, 1)和(0, -1)
• 垂直：(1, 0)和(-1, 0)
• 主对角线（\）：(1, 1)和(-1, -1)
• 副对角线（/）：(1, -1)和(-1, 1)

算法思路：对于每一个方向对（如水平方向的两个向量），我们从落子点开始，向正反两个方向延伸，统计连续相同棋子的数量。如果总数（正向+反向+1）>= 4，则获胜。

bool checkWin(int row, int col) { int player = board[row][col]; // 四个方向对：水平、垂直、主对角线、副对角线 vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {1, 1}, {1, -1}}; for (auto& dir : directions) { int dx = dir.first, dy = dir.second; int count = 1; // 包括刚落子的这颗棋子 // 正向延伸 for (int step = 1; step < 4; ++step) { int newRow = row + step * dx; int newCol = col + step * dy; if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || board[newRow][newCol] != player) { break; } count++; } // 反向延伸 for (int step = 1; step < 4; ++step) { int newRow = row - step * dx; int newCol = col - step * dy; if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || board[newRow][newCol] != player) { break; } count++; } // 判断是否连成四子 if (count >= 4) { return true; } } return false; }

实操心得：这里有一个非常容易出错的点——边界检查。在向某个方向延伸时，必须确保新的坐标(newRow, newCol)没有超出棋盘范围[0, rows-1] x [0, cols-1]。if判断中几个条件的顺序也有讲究，一定要先做下标越界检查，然后再去访问board数组，否则会引发未定义行为或程序崩溃。这种“短路与”的判断顺序是防御性编程的基本功。

3.4 主流程与输入输出处理

最后，我们将所有模块串联起来，并处理输入输出。假设输入格式是：第一行两个整数 R C，第二行开始是一系列整数，代表落子列，直到游戏结束。

int main() { int R, C; cin >> R >> C; // 初始化游戏状态（代码见3.1节） // ... int moveCol; int step = 0; vector<int> moves; // 可选：记录每一步的列号，用于复盘或错误输出 while (cin >> moveCol) { moves.push_back(moveCol); step++; int result = dropPiece(moveCol); if (result == -1) { // 无效操作，根据题目要求处理，可能是输出错误并结束 cout << "Invalid move at step " << step << ": column " << moveCol << " is invalid or full." << endl; break; } else if (result == 1 || result == 2) { cout << "Player " << result << " wins after " << step << " moves!" << endl; printBoard(); // 打印最终棋盘 break; } else if (result == 3) { cout << "Game ended in a draw after " << step << " moves." << endl; printBoard(); break; } // result == 0, 游戏继续，读取下一步 // 可以在这里打印每一步后的棋盘，用于调试 // cout << "After move " << step << " (col " << moveCol << "):" << endl; // printBoard(); } // 如果输入序列结束了但游戏未结束（理论上不应该，但需考虑） // ... return 0; }

4. 边界条件与异常处理全攻略

代码能处理正常流程只是第一步，健壮的程序必须能优雅地处理各种边界和异常情况。以下是几个必须考虑的陷阱：

4.1 输入数据的鲁棒性处理

机试系统的输入可能不会像我们想象的那么“干净”。

• 列号索引：题目明确说了列号从0开始还是从1开始？如果从1开始，你需要在读入后col--。这是一个经典的“坑点”。
• 非法输入：输入中可能包含非数字字符，或者列号超出了[0, C-1]的范围。dropPiece函数已经做了列号合法性和列满的检查，并返回了-1。主函数需要根据题目要求决定如何处理这种无效输入：是直接判负，还是忽略并继续读取下一个？通常题目会说明，一旦出现非法操作，即判当前玩家输。所以我们的代码应该能在检测到result == -1时，立即判定另一方获胜。

  if (result == -1) { // 当前玩家进行了非法操作 int winner = (currentPlayer == 1) ? 2 : 1; // 对方获胜 cout << "Player " << winner << " wins due to invalid move by player " << currentPlayer << endl; break; }

• 输入序列提前结束：如果输入序列用完了，游戏还没结束怎么办？这取决于题目定义。可能是平局，也可能是未完成。我们的主循环while (cin >> moveCol)会自然结束，我们可以在循环外补充状态判断。

4.2 棋盘状态的完整性校验

• 平局判断的时机：我们的平局判断是在每次落子后，检查是否所有列都满了。这是正确的。但要注意，获胜检查必须在平局检查之前。因为有可能最后一步落子同时导致棋盘被填满和四子连珠，此时应该判定为获胜，而不是平局。
• 多线程/并发幻觉：虽然本题是单线程顺序输入，但要养成“状态原子性”的思维。即，dropPiece函数执行期间，board和colHeight的状态应该被视为一个整体，不能被分割。在这个简单场景下，就是确保一次落子操作（检查、放置、更新高度、检查胜负）是连贯的。

4.3 性能与可扩展性思考

虽然本题棋盘小，但养成好习惯很重要。

• 时间复杂度：每次落子，dropPiece中checkWin是O(1)的（固定检查4个方向，每个方向最多延伸3步），平局检查是O(C)的。总体是线性的，完全足够。
• 空间复杂度：O(R*C)，就是棋盘本身。
• 如果棋盘非常大：比如1000x1000，频繁的平局检查（O(C)）可能成为瓶颈。可以维护一个计数器piecesCount，每成功落子一次就加1，当piecesCount == R * C时即为平局，将平局判断优化为O(1)。

5. 从解题到工程：代码风格与测试心得

写出能AC的代码是目标，但写出清晰、健壮、可维护的代码是本事。

5.1 模块化与代码组织

将不同的功能封装成函数，如initializeBoard,printBoard,dropPiece,checkWin。这使主逻辑清晰，也便于单独测试每个函数。例如，你可以写一个单元测试来专门验证checkWin在各种连珠情况下的正确性。

5.2 防御性编程与断言

在关键位置加入断言或严谨的校验。

int row = colHeight[col]; // 防御性断言，理论上colHeight[col] < rows 已由前文保证 assert(row >= 0 && row < rows && col >=0 && col < cols); board[row][col] = currentPlayer;

在调试版本中，这能帮你快速定位逻辑错误。

5.3 全面的测试用例设计

不要只依赖题目给的样例。自己设计测试用例覆盖各种场景：

1. 正常获胜：分别测试水平、垂直、两条对角线获胜。
2. 边界获胜：棋子在棋盘边缘连成四子。
3. 最后一步获胜：填满棋盘前一步获胜。
4. 最后一步平局：恰好填满棋盘且无人获胜。
5. 非法输入：列号过小、过大、列已满时落子。
6. 长序列测试：随机生成很长的合法序列，确保程序不崩溃、内存不泄漏。

一个简单的测试方法是将棋盘初始化，然后硬编码一系列落子步骤，观察输出是否符合预期。

void testCase1() { // 测试水平获胜 rows=6; cols=7; // ... 初始化 vector<int> moves = {3, 3, 2, 2, 1, 1, 0}; // 玩家1在0,1,2,3列连成一线 for (int col : moves) { int res = dropPiece(col); if (res == 1) { cout << "Test Horizontal Win PASSED" << endl; return; } } cout << "Test Horizontal Win FAILED" << endl; }

5.4 调试技巧：可视化与日志

当程序行为不符合预期时，printBoard()是你的最佳盟友。在每一步落子后打印棋盘，能让你清晰地看到棋局是如何演变的，快速定位是落子逻辑错了，还是获胜判断逻辑错了。

另外，可以在checkWin函数内部加入详细日志，打印出每次检查的方向和统计到的连续棋子数，这对于诊断复杂的边界情况特别有用。

6. 常见“坑点”与实战避坑指南

结合我自己和周围朋友踩过的坑，这里总结几个最容易出错的地方：

1. 索引混淆：这是最大的坑。行和列的索引是从0开始还是1开始？board[row][col]和colHeight[col]的关系是否正确？在纸上画一个3x3的小棋盘，手动模拟几次落子，确保你的索引计算和脑海中的图像一致。
2. 获胜判断的方向遗漏：只检查了水平和垂直，忘了两条对角线。或者检查对角线时，方向向量写错了。务必用(1,1)和(1,-1)这两组向量。
3. 获胜判断的计数错误：在checkWin中，连续棋子的计数应该从1开始（包括刚落下的子），然后向两个方向延伸。最容易错的是只向一个方向数了4个，或者数了5个才判断赢。我们的算法是“中心扩散法”，正确且简洁。
4. 平局判断的条件：平局是棋盘完全填满且没有获胜者。一定要先判断获胜，再判断平局。判断棋盘是否填满，高效的方法是检查colHeight数组是否每一项都等于rows，或者维护一个总棋子计数器。
5. 玩家切换的时机：一定要在确定本次落子没有导致游戏结束（即返回0）后，再切换当前玩家。如果在落子后立即切换，那么checkWin返回的获胜玩家标识就会错位。
6. 输入循环的终止条件：你的while循环是读整数，如果输入文件结束或出现非数字，cin >> moveCol会失败并退出循环。要确保在这种情况下，程序能输出一个合理的结果（例如“Incomplete game”），而不是无声无息地结束。

这道“竖直四子棋”的题目，本质上是一个状态模拟和条件判断问题。它考察的不是高深的算法，而是编程者严谨的思维、对细节的把握以及将自然语言规则无歧义地转化为代码的能力。把这些点都考虑到，实现干净，测试充分，拿到100%的通过率就是水到渠成的事情。编程实战中，这种把复杂问题分解为清晰模块，并逐一稳健实现的能力，远比死记硬背算法模板重要得多。