algorithm - 空の交差点のカウント

Question

私は、7 x 7 の盤面サイズ、w = 白石、b = 黒石で囲碁を実装しています。最終結果を数えたい。黒または白の石で囲まれた空のセルのみを数えます。

 0 1 2 3 4 5 6
0    b
1    b w  
2b b w   w
3  w       w
4    w     w
5      w w w
6

w と b で囲まれたすべての交点をカウントしたいということは、白い石のセル 2,3 3,2 3,3 3,4 4,3 4,4 と 0,0 0,1 1, をカウントしたいということです。黒い石の場合は 0 1,1。私が思いついたアルゴリズムはすべて複雑すぎます。

GNU アセンブラを使用して最終的なソリューションを実装します。アセンブリ言語の学習を始めたばかりなので、複雑にしたくありません。アルゴリズムはループと配列を使用できますが、再帰または関数呼び出しは使用できません。

この問題を解決するための線形代数の単純なアルゴリズムがあるかどうかを確認したかったのですが、再帰や関数呼び出しを使用しない単純なアルゴリズムを説明していただければ幸いです。

score 2 · Accepted Answer

フラッドフィルタイプのアルゴリズムが適用される場合があります。

最初の割り当てられていないセルを見つけます。
セルが空の場合は、そこから塗りつぶし、エッジセルまたは占有セルで停止します。
1. 遭遇した最初の占有セルについて、占有者の色を記録します。
2. 遭遇した占有セルが異なる色である場合、複数の色が関与していることを記録します。
3. 塗りつぶした後、検出された色が 1 つだけの場合は、領域全体をその色に属するものとしてマークします。領域内の空のセルの数がカウントに追加されます。
すべてのセルが割り当てられるまで、手順 1 から繰り返します。

フラッドフィルは、次のようなかなり標準的なアルゴリズムです。

開始セルをスタックにプッシュします。
スタックが空でない間:
1. そこからセルをポップします。
2. セルがまだ処理されていない場合 (つまり、この場合は未割り当て):
  1. それを処理します (つまり、この場合はその色を見てください)。
  2. すべての隣接ノードをスタックにプッシュします。

これらのアルゴリズムでは、ボードが目に見えない「エッジ」セルのレイヤーで囲まれていると、より簡単になることに注意してください。アルゴリズムの目的上、エッジセルと占有セルには隣接セルがありません。

score 0 · Accepted Answer

次のような空のスペースで形成された形状のエッジに沿って移動するアルゴリズムを試してみます。

次に、図形を使用して、各プレーヤーが所有するスペースの数を決定できます。

この質問には「宿題」というタグが付けられているため、さらに考えなければならないことがあります。

 0 1 2 3 4 5 6
0
1  w w w w w w
2  w
3  w   b b b
4  w   b   b
5  w   b b b
6  w

2 に答える 2