Buscando 'burbujas' en una matriz 2D de caracteres en Java

Question

Tengo un problema en mi proyecto Go Game.

Tengo un tablero (goban), representado por una matriz de caracteres 2D. Antes de cada movimiento siguiente, me gustaría comprobar si hay "burbujas" en el conjunto. Bubble debe ser un área con 4 enlaces de caracteres idénticos rodeados en 4 direcciones por otro grupo de caracteres idénticos específicos. Si existe esta 'burbuja', los caracteres internos deberían reemplazarse por otros. Pero podría haber más áreas y no todas están encerradas. Por ejemplo, tengo este tablero:

 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 | + + + + + + + + + + + + + | 
    - - - - - - - - - - - - - - - 

y me gustaría encontrar la burbuja de X, contarlos y reemplazarlos con 'Z.

Lo he buscado en Google y creo que algún algoritmo de etiquetado de componentes conectados o FloodFill puede hacer el trabajo, pero no estoy seguro de cómo implementarlo. ¿Es este el camino o algo menos complicado podría resolverlo? Gracias

Editar: He intentado encontrar algún patrón que podría encontrar las áreas de las características específicas y contar sus libertades, pero siempre fracasaron cuando el lugar era de varias capas. Cambiar la estructura de datos podría ser la solución, pero si es posible, me gustaría hacerlo tal como está ahora.

Mi idea solución actual:

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

Aquí está un algoritmo (en pseudocódigo) que he utilizado para el análisis de imágenes similares necesidades:

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, a mantener una colección de conjuntos de puntos donde cada conjunto representa una "burbuja" de puntos contiguos en el tablero. Escanee cada ubicación en el tablero y si es una 'X' y aún no está en una región, cree una nueva región y una pila que contenga la ubicación y mientras haya algún elemento en la pila, visite sus vecinos buscando 'X' no visitadas , agregándolos a la nueva región y apilados como descubiertos.

Al final tendrá una colección de conjuntos de puntos, cada uno representa una "burbuja".

Answer 2

Usted puede hacer eso con un método recursivo , de hecho, el uso de la teoría deFloodFill.

Básicamente, ejecute su cuadrícula, y cada vez que encuentre una X, reemplácela por una Z, así como por sus 4 vecinos (si corresponde). Pero el truco es: en lugar de simplemente reemplazarlos y tener que repetir el bucle cada vez, llame al mismo método (llamando) nuevamente para hacerlo. La recursividad hará el resto.

Aquí es un (hecho rápidamente) versión pseudo-código de la misma: (asumiendo que su rejilla está indexado de 0 a xmax, de 0 a 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); 
} 

Por lo que yo sé, esto es la solución única para este problema, que funciona de forma extraña su burbuja es. La complejidad tampoco está mal.

Esto se puede optimizar aún más, ya que actualmente comprueba los caracteres que obviamente ya no contienen una X (porque acaban de ser reemplazados por Z).Esto se deja como ejercicio para el lector :)

(NB: El dragaminas juego, entre otros, se basa en que la solución)