在Java中尋找二維字符數組中的'氣泡'

Question

我正在處理我的Go Game項目中的問題。

我有一個董事會（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 | + + + + + + + + + + + + + | 
    - - - - - - - - - - - - - - - 

而且我想找到XS的泡沫，數了以「Z的替換它們。

我使用了它，我認爲一些連接組件標籤算法或FloodFill可以完成這項工作，但我不知道如何實現它。這是否可以解決這個問題？ 謝謝

編輯： 我試圖找到一些模式，可以找到特定字符的區域並計算其自由度，但它總是失敗時，位置是多層。 更改數據結構可能是解決方案，但如果可能的話，我想按現在的方式來完成。

我目前的解決方案的想法：

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

下面是一個算法（在僞代碼），我已經用了類似的圖像分析需要：

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，你保持集的集合每一組都代表板上連續點的「泡沫」。掃描板上的每個位置，如果它是一個'X'，並且它不在一個區域中，則創建一個新的區域和一個包含該位置的堆棧，並且在堆棧中有任何物品時，訪問其鄰居搜索未訪問的'X' ，將它們添加到新區域並按發現的方式堆疊。

最後，您將獲得一組點，每個點代表一個「泡沫」。

Answer 2

您可以使用遞歸方法，確實使用FloodFill理論。

基本上，貫穿你的網格，並且每當你找到一個X時，用Z和它的4個鄰居（如果適用）替換它。但訣竅是：而不是僅僅替換它們，並且每次都必須再次循環，再次調用相同的（調用）方法來完成它。遞歸性將完成剩下的工作。

這裏是它的一個（快速完成）的僞代碼版本： （假設你的網格索引值從0到XMAX，從0到YMAX）據我所知

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); 
} 

，這是唯一的解決方案這個問題，它適用於任何古怪的形狀你的泡沫是。複雜性也不錯。

這可以進一步優化，因爲它目前檢查顯然不再包含X的字符（因爲它們剛剛被Z替換）。這是作爲練習留給讀者:)

（注：該掃雷遊戲，除其他外，是基於解決方案）