Algorytm, aby znaleźć całkowitą liczbę połączonych zbiorów w macierzy
Chciałem wiedzieć, jaki algorytm powinienem tutaj zastosować. Czy aDFS robić?
Biorąc pod uwagę macierz 2-d. Znajdź całkowitą liczbę połączonych zestawów w tej macierzy.
Połączony zestaw można zdefiniować jako grupę komórek, która ma na sobie 1 i ma co najmniej jedną inną komórkę w tym zestawie, z którą współużytkują relację sąsiada. Komórka z 1 w niej i sąsiadującym sąsiadem mającym 1 w niej może być traktowana jako zestaw z jedną komórką w niej. Sąsiedzi mogą być zdefiniowani jako wszystkie komórki sąsiadujące z daną komórką w 8 możliwych kierunkach (tj. W kierunku N, W, E, S, NE, NW, SE, SW). Komórka nie jest sąsiadem sama w sobie.
Na przykład:
1 0 0 1
0 0 1 0
0 0 1 0
1 0 0 1
liczba połączonych zestawów wynosi 3
0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 0 0 1 0 1
0 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0
liczba podłączonych zestawów wynosi 9.