题目解析 一颗棋子的气就是它上下左右 「空点」的数量。 若一颗棋子不和其他棋子共享气，我们直接统计下其周围的「空点」的数量即可； 如果棋子和其他棋子共享气，那么我们可以使用 DFS/BFS\tt{DFS/BFS}DFS/BFS 把这一整块共享气的棋子全部找出来，然后把这些棋子周围的空点数量 XXX 统计出来，那么对于这块共享气的棋子每个棋子的气都是 XXX。 AC代码 复杂度分析 使用 DFS/BFS\tt{DFS/BFS}DFS/BFS 找出所有一个棋子及其共享气的棋子总的时间复杂度为 O(N2)\mathrm{O}(N^2)O(N2)； 使用 std::set 找出这块棋子周围的空点数量的时间复杂度为 O(N2log⁡N2)\mathrm{O}(N^2 \log{N^2})O(N2logN2)。 总的时间复杂度为 O(N2log⁡N2)\mathrm{O}(N^2 \log{N^2})O(N2logN2)。

作者用心了，第二幅图确实是一整局围棋下完的样子 这道题深搜广搜都可以，掌握好思路就行 由于搜过的棋子以后都不会再搜，所以时间复杂度为O(n2)O(n^2)O(n2)

前言 这是一篇比 std 难写的做法，思路简单但是实现难搞。 我之前做过类似的题 还有借一下这个地方，求条。 题解 题目意思很简单吧。 看到连通块，可以想到并查集维护每个连通块内的数量，然后再维护每个连通块的气，答案的时候直接输出 find(u) 的答案就可以了。 但是这是二维的，可以用 std::pair 存，但是我考虑到 std 常数巨大，这里用的是 hash 映射成一维的数。 代码： 然后找四个方向，看是不是相同的子，如果是就合并并查集。 算出并查集，然后就是气怎么解决。 考虑每个点上存有哪些连通块用了这口气，显然是要去重的，因为存的东西小，直接枚举存的。 直接枚举每颗棋子，往四个方向加入这颗子在并查集上的父亲（就是所在连通块）。 最后算的时候直接往父亲加就可以了。 答案就是前文说的，是这个连通块的气的个数，直接 find(u) 的结果。 时间复杂度 O(n2)O(n^2)O(n2)。 完整代码： 还有借一下这个地方，求条。

实际上思路并不难 具体过程如下： 1.用并查集合并成一个个连通块 2.计算出每个连通块的气数（用set记录每个相邻空白的坐标就行，比vector暴力更快，时间复杂度为 O(log⁡n)O(\log n)O(logn)，而且实现简单） ok开始实现