Javaの文字の2次元配列で 'bubbles'を検索する

Question

私はGo Gameプロジェクトの問題を扱っています。

私は2次元配列の文字で表されるボード（goban）を持っています。次の移動の前に、配列内の「バブル」をチェックしたいと思います。気泡は、特定の同一の文字の別のグループによって4方向に囲まれた同一の文字の4連結領域でなければなりません。 この「バブル」が存在する場合、内部の文字は他の文字に置き換えてください。しかし、より多くの領域が存在する可能性があり、それらのすべてが閉じられているわけではありません。 例えば、私はこのボードがあります。

 1 2 3 4 5 6 7 8 9 10 11 12 13 
    - - - - - - - - - - - - - - - 
A | + + + + + + + + + + + + + | 
B | + + + + + + + + + + + + + | 
C | + + + + + + + + + + + + + | 
D | + + + + + + + + + + + + + | 
E | + + + + + + + + + + + + + | 
F | + + O O O O + + + + + + + | 
G | + O X X X X O + + + + + + | 
H | + + O O X X O + + + + + + | 
I | + + + + O X X O + + + + + | 
J | + + + + O X O + + + + + + | 
K | + + + + + O + + + + + + + | 
L | + + + + + + + + + + + + + | 
M | + + + + + + + + + + + + + | 
    - - - - - - - - - - - - - - - 

をそして私は、Xのバブルを見つけ、それらを数えると「Zのでそれらを交換したいと思います。

私はそれを見つけました。私はいくつかのConnected-ComponentラベリングアルゴリズムやFloodFillがその仕事をすることができると思いますが、実装方法はわかりません。これは方法ですか、それともそれほど複雑ではないのでしょうか？ ありがとうございました

編集： 特定の文字の領域を見つけてその自由度を数えるパターンを見つけようとしましたが、場所が重複していると常に失敗しました。 データ構造を変更することが解決策になるかもしれませんが、可能であれば、今のようにしたいと思います。

私の現在のソリューションのアイデア：

regions = Collection<Set<Point>> 
foreach (Point p : allBoardLocations) 
    if (charAtLocation(p) != 'X') continue 
    foundInRegion = false 
    for (Set<Point> s : regions) 
    if (s.contains(p)) 
     foundInRegion=true 
     break; 
    if (!foundInRegion) 
    newRegion = new Set<Point>() 
    stack = new Stack<Point>() 
    stack.push(p) 
    while (!stack.empty()) 
     foreach (Point n : neighboringPoints(stack.pop())) 
     if (charAtLocation(n) == 'X') 
      if (!newRegion.contains(n)) 
      newRegion.add(n); 
      stack.push(n); 

Bascially、あなたはセットのコレクションを維持する：ここで

public void solve(){ 
if (boardContainsEnclosedAreas(goban, onMovePlayerStone, oppositePlayerStone){ 
    onMovePlayerScore += countElementsInAreaAndReplaceThem(onMovePlayerStone, 'Z'); 
} 
} 

public boolean boardContainsEnclosedAreas(char[][] playingBoard, char searchedChar, char surroundingChar){ 
// this method should find the bubble in the playingBoard array 
} 

public int countElementsInAreaAndReplaceThem(char searchedChar, char replacingChar){ 
// the method should go through the bubble and replace all inner chars 
// returns amount of replaced chars 
} 

Answer 1

が必要と私は似た画像解析に使用しましたアルゴリズム（擬似コードで）です各セットはボード上の連続ポイントの「バブル」を表します。ボード上の各位置をスキャンし、それが「X」であり、それがまだ領域内にない場合は、新たな領域およびその位置を含むスタックを作成し、スタック上にアイテムがある間、未訪問の「Xそれらを新しい領域に追加し、発見されたとおりにスタックします。

最後には、それぞれが「バブル」を表すポイントの集合があります。

Answer 2

あなたは確かにFLOODFILL理論を用いて、再帰方法でそれを行うことができます。

基本的にグリッドを走り、Xを見つけるたびに、それを4つの隣人（該当する場合）と置き換えます。しかし、そのトリックは、単にそれらを置き換え、毎回ループを繰り返す代わりに、同じ（呼び出し元）メソッドを再度呼び出すことです。再帰は残りを行います。 私の知る限りでは

int numberOfBubbles = 0; 

for (x = 0 to xmax) { 
    for (y = 0 to ymax) { 
     if (getCharAt(x, y) == "X") { // this if is needed because you want to count the bubbles. If not, you could just do handleBubble(x, y); 
      numberOfBubbles++; 
      handleBubble(x, y); 
     } 
    } 
} 

// Recursive method 
void handleBubble(int x, int y) { 
    if (getCharAt(x, y) != "X") { 
     return; // exit condition 
    } 

    getCharAt(x, y) = "Z";  
    if (x > 0) handleBubble(x-1, y); 
    if (x < xmax) handleBubble(x+1, y); 
    if (y > 0) handleBubble(x, y-1); 
    if (y < ymax) handleBubble(x, y+1); 
} 

（あなたのグリッドが0からYMAXに、XMAXに0からインデックスされると仮定すると）、これは次のとおりです。ここで

はそれを（迅速に行う）擬似コードのバージョンです 解決策この問題は、あなたの気泡がどんな奇妙な形状であっても機能します。複雑さも悪くない。

これは、現在、明らかにXが含まれていない文字（現在はZで置き換えられているため）をチェックしているため、さらに最適化できます。これは、読者への課題として残されている:)

（NB：掃海艇ゲーム、他の中で、そのソリューションに基づいています）