在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替换）。这是作为练习留给读者:)

（注：该扫雷游戏，除其他外，是基于解决方案）