c - 在围棋中清除棋盘的快速算法

Question

我目前正在编写一些代码来处理围棋板。围棋棋盘表示为一组颜色。该数组有size×size个条目，代表一个二维方板。

enum color {
    EMPTY,
    BLACK,
    WHITE,
};

struct go_board {
    unsigned int size;
    enum color intersections[];
};

移动时enum color player，适用以下程序：（见规则）

1. [...]
2. 如果 P 的颜色（垂直或水平）相邻的点从 P 到颜色 C 的点有一条路径（垂直或水平），则称点 P（不是颜色 C）到达 C。
3. 清除颜色是清空该颜色的所有未达到空的点的过程。
4. [...]
5. 一个动作包括 [...] 清除对手的颜色，然后清除自己的颜色。

我正在寻找一种快速（就计算复杂性和实际速度而言）算法来清除电路板。你能帮助我吗？

Answer 1

使用图像处理的洪水填充算法。首先，用空点播种并填充所有白色或空的位置；所有未填充白色石头的位置都将死亡。用黑色重复。

Answer 2

您可以保留对板上每个组的引用，并跟踪他们的自由度。对于每个添加的石头，您最多只需将 4 个组合并/更新在一起。是我还是这听起来像 O(k)？:)

（已编辑）