Number of Islands

Mapa jest podawana jako lista wierszy o jednakowej długości. Każdy znak to albo 1, czyli pole lądu, albo 0, czyli pole wody. Dwa pola lądu należą do tej samej wyspy, jeśli jedno z nich znajduje się bezpośrednio nad, pod, na lewo lub na prawo od drugiego. Pola stykające się tylko narożnikiem nie są połączone.

Weź mapę ["11000", "11000", "00100", "00011"]:

• cztery pola lądu w lewym górnym rogu tworzą jedną wyspę,
• pojedyncze pole w środkowym wierszu to druga wyspa, ponieważ styka się z pierwszą tylko narożnikiem,
• dwa pola w prawym dolnym rogu tworzą trzecią.

Mapa zawiera więc 3 wyspy.

Mapa jest w rzeczywistości grafem: każde pole lądu to węzeł, a krawędź łączy dwa pola lądu, które mają wspólny bok. Liczenie wysp oznacza liczenie spójnych składowych tego grafu. Za każdym razem, gdy znajdziesz nieodwiedzone jeszcze pole lądu, odkryjesz nową wyspę i zbadasz ją w całości, zanim przejdziesz dalej.

Napisz funkcję o nazwie numIslands, która przyjmuje grid, listę ciągów znaków złożonych z 1 (lądu) i 0 (wody), i zwraca liczbę wysp. Wyspa to grupa pól lądu połączonych ze sobą w górę, w dół, w lewo lub w prawo.

Na przykład ["01110", "01000", "00011", "11001"] zwraca 3: kształt w górnych wierszach, grupa po prawej i para w lewym dolnym rogu.

Ograniczenia: 1 <= liczba wierszy, liczba kolumn <= 150. Wszystkie wiersze mają tę samą długość.