P2710. 围棋的气

解题思路

正向思路概述

考虑正向的思路，即从棋子位置出发，计算每一个棋子上下左右的气的个数。以黑棋为例（白棋完全类似）。

避免重复计算

由于如例子所示的多个同色棋子共有气的情况的出现，假设某一个空位 (ni, nj) 是黑棋的共有气，为了不被重复计算，我们需要将 (ni, nj) 存入一个哈希集合 black_qi_set 中。那么，当下一次考虑到同一个空位 (ni, nj) 时，就不会多次储存了。

以黑棋为例的整体过程

1. 构建偏移数组 D = [(0, 1), (1, 0), (0, -1), (-1, 0)]，构建哈希集合 qi_set。 2. 遍历所有黑棋 (i, j)。 3. 对于每一个黑棋的位置 (i, j)，遍历偏移量 (di, dj)，计算近邻点 (ni, nj)。 4. 若 (ni, nj) 没有越界，且是空位（即既不为黑棋也不为白棋），则将 (ni, nj) 加入哈希集合 qi_set 中。 5. 所有遍历结束后，返回 len(qi_set) 即为黑棋的气的数量。

构造通用函数

由于白棋和黑棋计算气的过程是相似的，可以构造一个函数 cal_qi_num() 来计算气的个数：

逆向思路

除了正向思路以外，本题还存在逆向的思路，即从所有空位出发，查看这个空位的周围是否存在黑棋或白棋。这种做法同样需要用到哈希集合来完成，感兴趣的同学可以尝试。

类似于 【模拟】2025C-统计监控中 的做法。

复杂度分析

设黑棋有 B 颗、白棋有 W 颗，棋子总数记为 S = B + W。

cal_qi_num 函数对传入颜色的每颗棋子只做固定的 4 次近邻检查，每次检查包含两次哈希集合查询（近邻点是否为同色棋子、是否为异色棋子）和至多一次插入，均摊 O(1)。所以统计黑棋的气是 O(4B)，统计白棋的气是 O(4W)，两次调用合计 O(S)，时间与棋子总数成正比。由于棋盘固定为 19x19，S 最多 361，实际运算量是很小的常数级别。

空间方面，set_black、set_white 存放全部棋子坐标，set_qi 最多存下所有空交叉点，整体 O(S) 且受 361 个交叉点封顶。

哈希集合在这里有两个作用：一是让“某个交叉点上有没有棋子”的判断变成平均 O(1) 的查询，不必构建整张棋盘的二维数组也能快速判定；二是对多颗同色棋子共享的气自动去重，保证同一口共有气只被计数一次，这正是正文强调用集合而不用计数器累加的原因。