1

私は現在、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. 移動は、[...]対戦相手の色をクリアしてから、自分の色をクリアすることで構成されます。

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

4

2 に答える 2

3

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

于 2013-02-12T11:08:57.137 に答える
0

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

(編集)

于 2014-03-27T11:04:01.143 に答える