Oto przykład (licząc czarnych):Jak liczyć grupy tych samych komórek w tablicy 2d?
wejściowe:
wyjściowa:
5 4 // 5 groups (4 squares each)
1 1 // 1 group containing 1 square
Na razie nie mogę wymyślić nic lepszego niż bolesne dla iteracja. Czy byłoby możliwe uzyskanie tych grup w sposób rekurencyjny? Dzięki
Na początku każda komórka będzie "nieodwiedzana".
Chciałbym iterować przez komórki, dopóki nie spotkasz "nieodwiedzonych" czarnych komórek. Każda biała komórka, którą trafiłeś do tego momentu,
Po uderzeniu w czarną komórkę, "rozwinąć" ją do wszystkich kierunków, jeśli to możliwe (podobnie do "wypełnienia"). Rozszerzasz się tak długo, jak możesz i zaznaczasz wszystkie odwiedzone komórki jako "odwiedzone". Po wykonaniu tej czynności policzysz liczbę zainfekowanych czarnych komórek i wiesz, jak duża była ta grupa. Po wykryciu grupy przechodzisz do następnej "nieodwiedzonej" czarnej komórki.
Możesz użyć algorytmu dla connected component labeling z 4-łączliwością
Nie widzę wejścia! – elyashiv
Co liczy się jako "grupa"? Prostokąty? Ciągłe czarne obszary? – phimuemue
cóż, zdjęcie jest wprowadzeniem tablicy 2d, grupa czarnych obszarów to bloki czarnych kwadratów leżących obok siebie (nie liczyć diagonalnie) – Patryk