Number of Islands

Eine Karte kommt als Liste gleich langer Zeilen. Jedes Zeichen ist entweder 1, ein Feld Land, oder 0, ein Feld Wasser. Zwei Landfelder gehören zur selben Insel, wenn eines direkt oberhalb, unterhalb, links oder rechts vom anderen liegt. Felder, die sich nur an einer Ecke berühren, sind nicht verbunden.

Betrachte die Karte ["11000", "11000", "00100", "00011"]:

• Die vier Landfelder in der oberen linken Ecke bilden eine Insel,
• das einzelne Feld in der mittleren Zeile ist eine zweite Insel, da es die erste nur an einer Ecke berührt,
• die beiden Felder unten rechts bilden eine dritte.

Die Karte enthält also 3 Inseln.

Die Karte ist eigentlich ein Graph: Jedes Landfeld ist ein Knoten, und eine Kante verbindet zwei Landfelder, die eine Seite gemeinsam haben. Inseln zu zählen bedeutet, die zusammenhängenden Komponenten dieses Graphen zu zählen. Jedes Mal, wenn du ein Landfeld findest, das du noch nicht besucht hast, hast du eine neue Insel gefunden, und du erkundest sie vollständig, bevor du weitermachst.

Schreibe eine Funktion namens numIslands, die grid erhält, eine Liste von Zeichenketten aus 1 (Land) und 0 (Wasser), und die Anzahl der Inseln zurückgibt. Eine Insel ist eine Gruppe von Landfeldern, die nach oben, unten, links oder rechts miteinander verbunden sind.

Zum Beispiel gibt ["01110", "01000", "00011", "11001"] den Wert 3 zurück: die Form in den oberen Zeilen, die Gruppe rechts und das Paar in der unteren linken Ecke.

Einschränkungen: 1 <= Anzahl der Zeilen, Anzahl der Spalten <= 150. Alle Zeilen haben dieselbe Länge.