Number of Islands

Q: Quelle est la complexité temporelle du problème du nombre d’îles ?

O(rows × cols). Le parcours examine chaque case une seule fois, et chaque case terrestre est ajoutée une seule fois à la pile ou à la file, puis vérifie quatre voisines. Les marques seen et la pile ou la file utilisent un espace O(rows × cols) sur une carte entièrement terrestre.

Q: Faut-il utiliser BFS ou DFS pour le nombre d’îles ?

Les deux sont corrects en termes de temps et d’espace, car le comptage nécessite seulement que chaque case d’une île soit marquée. Le BFS avec une file ne fait jamais de récursion ; le DFS est tout aussi sûr lorsqu’il utilise une pile explicite.

Q: Peux-tu résoudre « Nombre d’îles » avec union-find ?

Oui. Placez chaque case terrestre dans son propre ensemble et commencez le compte au nombre de cases terrestres. Réunissez chaque paire de cases terrestres voisines et diminuez le compte de un chaque fois qu’une réunion relie deux ensembles différents. Avec la compression de chemin, le temps d’exécution est proche de O(rows × cols).

Q: Peux-tu compter les îles sans tableau `seen` séparé ?

Oui, si tu peux modifier la carte : transforme chaque case terrestre en eau dès que tu l’atteins. De nombreux langages ne permettent pas de modifier les chaînes sur place, donc tu copies d’abord les lignes dans une grille de caractères, ce qui prend autant d’espace que les marques des cases déjà vues.

MoyenGraphes

+10

Vous recevez une carte sous forme d’une liste de chaînes de même longueur, où '1' représente une case de terre et '0' une case d’eau. Deux cases de terre appartiennent à la même île lorsqu’elles partagent un côté : en haut, en bas, à gauche ou à droite. Les cases qui se touchent uniquement par un coin ne sont pas connectées. Renvoyez le nombre d’îles.

Fonction

numIslands(grid: string-array) → integer

gridstring-array: la carte, une chaîne par ligne
Renvoieinteger: le nombre d’îles

Contraintes

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Chaque ligne a la même longueur.
Chaque caractère est '0' ou '1'.

Exemples

Entrée: grid = ["11000", "11000", "00100", "00011"]
Sortie: 3
Explication: Les quatre carrés en haut à gauche forment une île. Le carré du milieu de la troisième rangée ne les touche que par un coin ; c’est donc une deuxième île. La paire en bas à droite constitue la troisième.

Pour aller plus loin

La terre apparaît maintenant carré par carré sur une carte d’eau. Peux-tu indiquer le nombre d’îles après l’apparition de chaque nouveau carré sans parcourir à nouveau toute la carte ?

Solution

Considérez chaque case terrestre comme un nœud relié aux cases terrestres qui l’entourent : une île est une seule zone connexe. Parcourez la carte et, chaque fois que vous atteignez une case terrestre que vous n’avez pas encore vue, comptez une nouvelle île et remplissez-la par propagation, en marquant chacune de ses cases afin que le parcours ne la compte plus.

Remplissage par diffusion avec une pile explicite (DFS)

Intuition

Une case de terre non marquée ne peut pas appartenir à une île que tu as déjà comptée, car le comptage d’une île la marque entièrement. Elle commence donc une nouvelle île. Une pile que tu gères toi-même marque le reste : chaque case que tu dépiles empile ses voisines de terre non marquées et, lorsque la pile est vide, toute l’île est marquée.

Ta propre pile est importante, car un remplissage récursif peut atteindre une profondeur de 22 500 appels sur une carte de 150 × 150 entièrement constituée de terre. Chaque case est empilée au plus une fois et vérifie quatre voisines, donc le temps d’exécution est en O(rows × cols). Les marquages et la pile occupent un espace en O(rows × cols) lorsque la carte est entièrement constituée de terre.

Algorithme

Créer une marque de visite pour chaque case et définir le compteur à 0.
Parcourir chaque case, en ignorant l’eau et les cases déjà visitées.
Sur une terre non visitée, ajouter 1 au compteur, marquer la case et l’empiler.
Tant que la pile n’est pas vide, dépiler une case et empiler chaque voisine située dans la carte qui est une terre non visitée, en la marquant avant de l’empiler.
Renvoyer le compteur lorsque le parcours est terminé.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            # Land that no island has claimed yet: a new island.
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        # Mark on push, so no square enters the stack twice.
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Remplissage par diffusion avec une file d’attente (BFS)

Intuition

Le comptage fonctionne de la même manière ; seul l’ordre de visite change. Une file prend les cases à l’avant et ajoute les cases voisines de terre non marquées à l’arrière, elle visite donc l’île par anneaux : la première case, puis chaque case à une étape de distance, puis à deux étapes de distance. Chaque case est tout de même visitée une fois, en O(rows × cols) en temps et en espace.

L’ordre en anneaux donne la distance de chaque case au point de départ, ainsi la même boucle répond aux questions de plus court chemin sur une grille avec un nombre supplémentaire par case.

Algorithme

Crée un indicateur de visite pour chaque case et initialise le compteur à 0.
Parcours chaque case, en ignorant l’eau et les cases déjà visitées.
Sur une terre non visitée, ajoute 1 au compteur, marque la case et place-la dans une file vide.
Tant que la file contient des cases, prends-en une à l’avant et ajoute à l’arrière chaque voisine située dans la carte qui est une terre non visitée, en la marquant au moment de l’ajouter.
Renvoie le compteur à la fin du parcours.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Pièges et cas limites

Marquer une case lorsqu’on la retire de la pile ou de la file plutôt que lorsqu’on l’y ajoute. La même case est alors ajoutée plusieurs fois.
Comparer une case au nombre 1 au lieu du caractère '1'. Chaque ligne est une chaîne, donc chaque case est un caractère.
Lire une case voisine avant de vérifier 0 ≤ row < rows et 0 ≤ col < cols. Une case de terre située au bord lit alors en dehors de la carte.
Écrire le remplissage de manière récursive. Par défaut, Python s’arrête après 1,000 appels, et d’autres langages peuvent provoquer un dépassement de pile sur une grande île.
Retirer le premier élément d’une liste Python avec pop(0), ce qui prend un temps proportionnel à la longueur de la liste. Utilisez collections.deque et popleft().

Questions fréquentes4

Quelle est la complexité temporelle du problème du nombre d’îles ?

O(rows × cols). Le parcours examine chaque case une seule fois, et chaque case terrestre est ajoutée une seule fois à la pile ou à la file, puis vérifie quatre voisines. Les marques seen et la pile ou la file utilisent un espace O(rows × cols) sur une carte entièrement terrestre.

Faut-il utiliser BFS ou DFS pour le nombre d’îles ?

Les deux sont corrects en termes de temps et d’espace, car le comptage nécessite seulement que chaque case d’une île soit marquée. Le BFS avec une file ne fait jamais de récursion ; le DFS est tout aussi sûr lorsqu’il utilise une pile explicite.

Peux-tu résoudre « Nombre d’îles » avec union-find ?

Oui. Placez chaque case terrestre dans son propre ensemble et commencez le compte au nombre de cases terrestres. Réunissez chaque paire de cases terrestres voisines et diminuez le compte de un chaque fois qu’une réunion relie deux ensembles différents. Avec la compression de chemin, le temps d’exécution est proche de O(rows × cols).

Peux-tu compter les îles sans tableau `seen` séparé ?

Oui, si tu peux modifier la carte : transforme chaque case terrestre en eau dès que tu l’atteins. De nombreux langages ne permettent pas de modifier les chaînes sur place, donc tu copies d’abord les lignes dans une grille de caractères, ce qui prend autant d’espace que les marques des cases déjà vues.

def numIslands(grid):
    # Écrivez le code ici

Test #1

Test #2

Argument

grid = ["11000", "11000", "00100", "00011"]

Résultat attendu