c - Goでボードをクリアするための高速アルゴリズム

Question

私は現在、Goボードを処理するためのコードを書いています。碁盤は色の配列として表されます。配列にはsize×sizeエントリがあり、2次元の正方形のボードを表します。

enum color {
    EMPTY,
    BLACK,
    WHITE,
};

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

移動する場合enum color player、次の手順が適用されます:(ルールを参照）

1. [...]
2. Pから色Cの点へのPの色の（垂直または水平）隣接する点の経路がある場合、色Cではなく点PはCに到達すると言われます。
3. 色をクリアすることは、空に達しないその色のすべてのポイントを空にするプロセスです。
4. [...]
5. 移動は、[...]対戦相手の色をクリアしてから、自分の色をクリアすることで構成されます。

ボードをクリアするための高速な（計算の複雑さと実際の速度の点で）アルゴリズムを探しています。手伝って頂けますか？

Answer 1

画像処理のフラッドフィリングアルゴリズムを使用します。まず、空のポイントをシードし、白または空のすべての位置を埋めます。白い石で埋められていないポジションはすべて死んでしまいます。黒で繰り返します。

Answer 2

ボード上の各グループへの参照を保持し、それらの自由を追跡することができます。追加された石ごとに、最大4つのグループをマージ/更新するだけです。それは私ですか、それともこれはO（k）のように聞こえますか？:)

（編集）