Number of Islands

Une carte se présente sous la forme d’une liste de lignes de longueur égale. Chaque caractère est soit 1, une case de terre, soit 0, une case d’eau. Deux cases de terre appartiennent à la même île lorsque l’une se trouve directement au-dessus, en dessous, à gauche ou à droite de l’autre. Les cases qui se touchent uniquement par un coin ne sont pas connectées.

Considère la carte ["11000", "11000", "00100", "00011"] :

• les quatre cases de terre dans le coin supérieur gauche forment une île,
• la case unique de la ligne du milieu forme une deuxième île, puisqu’elle ne touche la première que par un coin,
• les deux cases dans le coin inférieur droit forment une troisième île.

La carte contient donc 3 îles.

La carte est en réalité un graphe : chaque case de terre est un nœud, et une arête relie deux cases de terre qui partagent un côté. Compter les îles revient à compter les composantes connexes de ce graphe. Chaque fois que tu trouves une case de terre que tu n’as pas encore visitée, tu as trouvé une nouvelle île, et tu l’explores entièrement avant de continuer.

Écrivez une fonction nommée numIslands qui reçoit grid, une liste de chaînes composées de 1 (terre) et de 0 (eau), et renvoie le nombre d’îles. Une île est un groupe de cases terrestres reliées vers le haut, le bas, la gauche ou la droite.

Par exemple, ["01110", "01000", "00011", "11001"] renvoie 3 : la forme dans les rangées du haut, le groupe à droite et la paire dans le coin inférieur gauche.

Contraintes : 1 <= nombre de rangées, nombre de colonnes <= 150. Toutes les rangées ont la même longueur.