0

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

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

4

2 に答える 2

2

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

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

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

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

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

http://en.wikipedia.org/wiki/Flood_fillを参照

于 2012-04-18T05:29:27.460 に答える
0

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

  1. 空きスペースに隣接するピースから始めます。
  2. 隣接するすべてのスペースをテストすることにより、空のスペースによって形成される形状の外側の端に沿って移動します。
  3. ボードの端に遭遇した場合は、ボードの端に沿って移動を続けることができます。
  4. 形の境界に沿って黒と白の両方のピースに遭遇した場合、その形はどのプレーヤーにも属していません。
  5. それ以外の場合、輪郭を描いた図形は、すべてのボーダー ピースを所有するプレーヤーに属します。

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

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

 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
于 2012-04-18T05:34:12.423 に答える