在Java中搜索二维字符数组中的“bubbles”

Question

在Java中搜索二维字符数组中的“bubbles”

8

我正在处理我的围棋项目中的问题。

我有一个由字符的二维数组表示的棋盘（goban）。在每次下棋之前，我想检查数组中是否存在“气泡”。气泡应该是由相同字符组成的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'替换它们。

我已经搜索过了，我认为一些连通组件标记算法或洪水填充可以完成这项工作，但我不确定如何实现它。这是正确的方法还是有更简单的方法可以解决呢？谢谢

编辑：我试图找到一些模式，可以找到特定字符区域的位置并计算它们的自由度，但当位置多层时，它总是失败。改变数据结构可能是解决方案，但如果可能的话，我想保持现状。

我的当前解决方案思路：

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
}

- jC30

你有没有考虑过其他的数据结构？也许你可以创建一个链类，其中包含所有相同颜色的连接块。它将具有一些自由度，并且当自由度达到0时，该链将被移除。 - Jay Conrod

如果您能发布您的“期望输出”，那将是非常好的。 - Bhushan

2个回答

0

这是一个伪代码算法，我曾经用它来满足类似的图像分析需求：

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

基本上，您维护了一组点集合，其中每个集合表示棋盘上连续点的“气泡”。扫描棋盘上的每个位置，如果它是一个’X’并且它尚未在区域中，则创建一个新的区域和一个包含该位置的堆栈，同时访问其邻居以搜索未访问的‘X’，将它们添加到新区域和堆栈中作为已发现的元素。

最后，您将拥有一组点集合，每个表示一个“气泡”。

- maerics

@toto2：没错，谢谢。我只是想到什么就写什么，肯定有很多错误，只是想展示这个想法。 - maerics

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Guillaume · Accepted Answer

你可以使用递归方法，确实使用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）。这留给读者作为练习 :)

（注：扫雷游戏等基于该解决方案）