Wyszukiwanie 'bąbelków' w tablicy 2D znaków w Javie

Question

Mam do czynienia z problemem w moim projekcie Go Game.

Mam deskę (goban) reprezentowaną przez 2D Array of charars. Przed każdym następnym ruchem chciałbym sprawdzić "bańki" w tablicy. Bubble powinien być 4-połączonym obszarem identycznych znaków otoczonych w 4 kierunkach przez inną grupę konkretnych identycznych znaków. Jeśli ta "bańka" istnieje, postacie wewnątrz powinny zostać zastąpione przez inne. Ale może być więcej obszarów i nie wszystkie są zamknięte. Na przykład, mam ten dział:

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

I chciałbym, aby znaleźć bańki xs, policzyć je i zastąpić je „Z tych.

Mam googleed i myślę, że niektóre algorytm etykietowania Connected-component lub FloodFill może wykonać zadanie, ale nie jestem pewien, jak go wdrożyć. Czy w ten sposób lub coś mniej skomplikowanego może go rozwiązać? Dziękujemy

Edytuj: Próbowałem znaleźć wzór, który mógłby znaleźć obszary określonego charakteru i policzyć ich wolności, ale zawsze zawodził, gdy lokalizacja była wielowarstwowa. Zmiana struktury danych może być rozwiązaniem, ale jeśli to możliwe, chciałbym to zrobić tak jak teraz.

Mój obecny pomysł rozwiązanie:

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

Oto algorytm (w Pseudokod), które użyłem do podobnej analizy obrazu wymaga:

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, utrzymać kolekcję kompletów punkty, w których każdy zestaw reprezentuje "bąbel" sąsiednich punktów na planszy. Zeskanuj każdą lokalizację na planszy i jeśli jest to "X", a nie jest jeszcze w regionie, stwórz nowy region i stos zawierający jego lokalizację, a jeśli na stosie znajduje się jakikolwiek przedmiot, odwiedź sąsiadów szukających nieodwiedzonych "X" , dodając je do nowego regionu i stosu odkryte.

Na koniec otrzymasz kolekcję zestawów punktów, z których każdy reprezentuje "bąbelek".

Answer 2

Można to zrobić za pomocą metody rekurencyjne rzeczywiście używając flood fill teorię.

Zasadniczo, przebiegnij przez siatkę, a za każdym razem, gdy znajdziesz X, wymień go na Z, a także na 4 sąsiadów (jeśli dotyczy). Ale sztuczka polega na tym, że zamiast po prostu zastępować je i ponownie za każdym razem uruchamiać pętlę, należy ponownie wywołać tę samą metodę (wywoływanie), aby to zrobić. Rekurencyjność zajmie się resztą.

Oto (szybko zrobione) wersja pseudo-kod nim: (zakładając, że siatka jest indeksowany od 0 do Xmax, od 0 do 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); 
} 

O ile mi wiadomo, jest to Jedynym rozwiązaniem tego problemu jest , który działa niezależnie od kształtu twojej bańki. Złożoność też nie jest zła.

Można to zoptymalizować, ponieważ obecnie sprawdza znaki, które w oczywisty sposób nie zawierają już litery X (ponieważ zostały zastąpione przez Z).To pozostawiamy jako ćwiczenie dla czytelnika :)

(Uwaga: trałowiec grze, między innymi, opiera się na tym roztworze)