java - 在 Java 的二维字符数组中搜索 'bubbles'

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's 替换它们。

我用谷歌搜索了一下，我认为某些连通分量标记算法或 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

您可以使用递归 方法来做到这一点，实际上是使用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 替换)。这是留给读者的练习:)

(注意:扫雷 游戏等都基于该解决方案)