Swim in Rising Water

Q: Quelle est la complexité temporelle de Swim in Rising Water ?

O(n² log n) avec l'algorithme de Dijkstra : chacune des n² cellules est insérée puis extraite du tas au plus une fois, celui-ci contenant jusqu'à n² éléments. La recherche dichotomique du niveau de l'eau a la même complexité, avec environ log2(n²) remplissages par propagation de O(n²) chacun. Les deux utilisent O(n²) mémoire pour les marques de visite et le tas ou la pile.

Q: Pourquoi l’algorithme de Dijkstra fonctionne-t-il lorsque le coût est celui de la cellule la plus élevée ?

Dijkstra nécessite une propriété : prolonger un itinéraire ne réduit jamais son coût. Ici, le nouveau coût est max(t, height) , qui n’est jamais inférieur à t , donc cette propriété est vérifiée. C’est pourquoi, dès qu’une cellule quitte le tas pour la première fois, son temps est définitif et tu peux t’arrêter à la cible.

Q: Peut-on résoudre le problème « Can Swim in Rising Water » avec une recherche binaire ?

Oui. La possibilité de traverser au niveau t est fausse pour tous les niveaux inférieurs à la réponse, et vraie à partir de la réponse. Une recherche binaire sur t , avec un remplissage par propagation comme test, trouve la réponse en environ log2(n²) tests : 14 pour une grille de 100 × 100.

Q: Peut-on résoudre « Swim in Rising Water » avec union-find ?

Oui. Ouvrez les cellules par ordre de hauteur, reliez chaque nouvelle cellule à ses voisines ouvertes et arrêtez-vous dès que le coin supérieur gauche et le coin inférieur droit appartiennent au même ensemble. La hauteur de la dernière cellule ouverte est la réponse. Puisque la grille contient une fois chaque valeur de 0 à n²-1 , une table associant chaque hauteur à une cellule donne l’ordre d’ouverture sans tri.

DifficilePlus courts chemins Tas Recherche binaire

+10

On vous donne une grille n × n de hauteurs contenant chaque nombre de 0 à n²-1 exactement une fois, sous forme d’une liste de lignes. La pluie commence à l’instant 0 et, à l’instant t, l’eau atteint partout la hauteur t, si bien que chaque cellule de hauteur inférieure ou égale à t est sous l’eau. Vous commencez dans la cellule en haut à gauche. Vous pouvez nager d’une cellule à une cellule qui partage un côté avec elle lorsque les deux sont sous l’eau, et la nage ne prend pas de temps. Renvoyez le premier instant auquel vous pouvez vous trouver dans la cellule en bas à droite.

Fonction

swimInWater(grid: integer-2d-array) → integer

gridinteger-2d-array: les hauteurs, sous forme d’une liste de n lignes de n nombres
Renvoieinteger: le moment le plus tôt où tu peux atteindre la cellule en bas à droite

Contraintes

n == grid.length == grid[i].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
Chaque valeur de 0 à n²-1 apparaît exactement une fois.

Exemples

Entrée: grid = [[0, 2], [3, 1]]
Sortie: 2
Explication: En passant par la cellule en haut à droite, l’itinéraire est 0, 2, 1, et sa cellule la plus haute est 2. En passant par la cellule en bas à gauche, il est 0, 3, 1, et sa cellule la plus haute est 3. À l’instant 2, le premier itinéraire est sous l’eau, donc la réponse est 2.

+13 tests cachés à la soumission

Pour aller plus loin

Si les hauteurs pouvaient se répéter et atteindre 10^9, laquelle de tes approches fonctionnerait toujours sans modification, et sur quoi effectuerais-tu une recherche binaire ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Le temps nécessaire à un itinéraire correspond à la cellule la plus élevée qu’il traverse, car l’eau doit recouvrir chaque cellule sur votre chemin. La tâche consiste donc à trouver l’itinéraire entre les coins dont la cellule la plus élevée est la moins élevée possible : un chemin le plus court dont le coût est son maximum, et non sa somme. Vous pouvez monter le niveau de l’eau étape par étape et effectuer un test, faire une recherche dichotomique sur le niveau de l’eau à l’aide du même test, ou exécuter l’algorithme de Dijkstra en prenant la cellule la plus élevée comme coût.

Faites monter l’eau une étape à la fois

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fixe un niveau d’eau t. Les cellules que tu peux atteindre sont celles dont la hauteur est au plus t et qui sont reliées au départ par de telles cellules. Un remplissage par propagation depuis le coin supérieur gauche permet de les trouver : ajoute le départ, retire une cellule, puis ajoute chaque voisine non visitée dont la hauteur est au plus t. Si le coin inférieur droit est visité, le niveau t suffit.

La réponse est le plus petit t pour lequel le remplissage par propagation atteint l’arrivée. Il ne peut pas être inférieur à la hauteur du coin le plus élevé, max(grid[0][0], grid[n-1][n-1]), puisque les deux coins doivent être sous l’eau. Commence à ce niveau et ajoute 1 jusqu’à ce que le remplissage réussisse. Le premier niveau qui fonctionne est la réponse, car la montée de l’eau ne fait qu’ouvrir des cellules et n’en ferme jamais : un niveau qui fonctionne continue de fonctionner.

Chaque test coûte O(n²), et l’eau peut monter presque n² fois avant que le remplissage atteigne l’arrivée. Sur une grille de 100 × 100, cela représente jusqu’à 10^4 niveaux × 10^4 cellules, soit environ 10^8 visites de cellules. Dans les grands tests, les coins contiennent 0 et 1 et les réponses se situent entre 4,950 et 9,998 : des milliers de remplissages par propagation complets sont donc exécutés avant que la réponse ne soit trouvée.

Algorithme

Définis t comme la plus grande des deux hauteurs des coins.
Effectue un remplissage par propagation depuis le coin supérieur gauche, en traversant les cellules dont la hauteur est au plus t, avec une pile explicite et une marque de visite par cellule.
Si le remplissage atteint le coin inférieur droit, renvoie t.
Sinon, ajoute 1 à t et recommence le remplissage.

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # You cannot finish before the water covers both corners.
    t = max(grid[0][0], grid[n - 1][n - 1])
    # Raise the water one step at a time until a way through opens.
    while not canReach(grid, t):
        t += 1
    return t

Recherche binaire sur le niveau de l’eau

Intuition

Le test de la première approche a une forme utile. Il échoue pour tous les niveaux inférieurs à la réponse et réussit pour tous les niveaux à partir de la réponse. La recherche dichotomique trouve une question à réponse oui ou non qui bascule une seule fois, de non à oui, en un nombre logarithmique d’essais.

Fais une recherche entre lo, le coin le plus élevé, et hi = n²-1, la cellule la plus élevée, où toute la grille est sous l’eau et où le test doit réussir. Teste le niveau médian. Si tu peux passer, la réponse est au plus mid, donc définis hi = mid ; sinon, elle est supérieure à mid, donc définis lo = mid + 1. Lorsque les deux se rejoignent, ce niveau est la réponse.

Dans l’exemple de grille 5 × 5, lo = 6 et hi = 24. Le niveau 15 échoue, car la zone supérieure est enclavée, donc lo = 16. Les niveaux 20, 18, 17 et 16 réussissent tous, ce qui fait descendre hi à 16 ; la recherche se termine à 16 après cinq remplissages par propagation.

Une grille de 100 × 100 comporte 10^4 niveaux : environ 14 tests suffisent donc à déterminer la réponse, chacun en O(n²), soit environ 1.4 × 10^5 visites de cellules au lieu de 10^8. Garde le remplissage par propagation itératif. Un grand test consiste en un couloir sinueux d’environ 5,000 cellules, bien plus profond que la limite de 1,000 appels imbriqués de Python.

Algorithme

Définissez lo sur la hauteur du coin le plus élevé et hi sur n²-1.
Tant que lo < hi, prenez mid = (lo + hi) / 2, arrondi à l’entier inférieur.
Effectuez un remplissage par propagation au niveau mid. S’il atteint le coin inférieur droit, définissez hi = mid ; sinon, définissez lo = mid + 1.
Retournez lo.

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # The answer lies between the higher corner and the highest cell.
    lo = max(grid[0][0], grid[n - 1][n - 1])
    hi = n * n - 1
    # canReach is false below the answer and true from it on: find the first true.
    while lo < hi:
        mid = (lo + hi) // 2
        if canReach(grid, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Dijkstra sur la cellule la plus haute du parcours

Intuition

Considère la grille comme un graphe et attribue un coût à chaque itinéraire : sa cellule la plus élevée, et non la somme de ses étapes. L’algorithme de Dijkstra fonctionne toujours avec ce coût, car prolonger un itinéraire ne le rend jamais moins coûteux. Le coût de l’itinéraire plus long est max(old cost, new height), jamais inférieur à l’ancien coût, et c’est la seule propriété dont Dijkstra a besoin.

Garde un tas min de cellules, ordonnées selon leur temps, c’est-à-dire la cellule la plus élevée du meilleur itinéraire trouvé jusqu’à elles. Commence avec la cellule en haut à gauche au temps grid[0][0]. Extrais la cellule dont le temps t est le plus petit ; chaque voisine que tu n’as pas encore vue reçoit le temps max(t, its height). Quand la cellule en bas à droite sort du tas, son temps est la réponse.

Tu peux marquer une cellule comme vue dès que tu l’ajoutes au tas. Les cellules sortent du tas par ordre de temps : la première cellule qui atteint une voisine a le temps le plus petit parmi toutes celles qui l’atteindront, et le temps qu’elle attribue à cette voisine est donc le meilleur possible. Un itinéraire ultérieur arrive avec un temps au moins aussi grand. Ainsi, chaque cellule entre une seule fois dans le tas, avec son temps définitif.

C’est la montée des eaux, étape par étape. Le tas contient le bord de la zone que tu peux atteindre, et extraire sa cellule la plus basse revient à faire monter l’eau juste assez pour y accéder. Dans l’exemple 5 × 5, les extractions donnent 0, 1, 2, 3, 4, 5, puis la porte à 16. Ensuite, chaque cellule sur le chemin du détour reçoit le temps 16, et la cellule en bas à droite sort du tas avec le temps 16 avant toute cellule plus élevée.

Chacune des n² cellules est ajoutée et extraite au plus une fois, en O(log n) à chaque fois : le temps d’exécution est donc O(n² log n), et la recherche s’arrête dès que la cible est extraite.

Algorithme

Marquez le coin supérieur gauche comme visité et empilez-le avec le temps grid[0][0].
Retirez la cellule ayant le plus petit temps t. Si c’est le coin inférieur droit, renvoyez t.
Pour chaque voisin qui n’a pas encore été visité, marquez-le et empilez-le avec le temps max(t, its height).
Répétez à partir de l’étape 2.

import heapq


def swimInWater(grid):
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    # (time, row, col): the time is the highest cell on the best path found to that cell.
    heap = [(grid[0][0], 0, 0)]
    while True:
        t, r, c = heapq.heappop(heap)
        # Cells leave the heap in order of time, so this is the earliest you can be here.
        if r == n - 1 and c == n - 1:
            return t
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
                # Reached for the first time from the cell with the smallest time:
                # no later route can arrive earlier, so mark it now.
                seen[nr][nc] = True
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))

Pièges et cas limites

La plupart des mauvaises réponses viennent d’un coin oublié, d’un coût additionné au lieu de prendre le maximum, ou d’une recherche qui s’arrête trop tôt.

Ne pas tenir compte de la hauteur de la case de départ. Tu ne peux pas te trouver en haut à gauche avant qu’elle soit sous l’eau ; la réponse est donc au moins grid[0][0]. Avec [[3, 0], [1, 2]], la réponse est 3.
Ne pas tenir compte de la hauteur de la cible. Le coin en bas à droite doit lui aussi être sous l’eau ; la réponse est donc au moins grid[n-1][n-1].
Aller de façon gloutonne vers le voisin le plus bas de la case actuelle. Le meilleur itinéraire peut monter jusqu’à une porte, puis faire un long détour, comme dans l’exemple 5 × 5. Seule une recherche sur toute la frontière de la zone atteinte permet de le trouver.
Additionner les hauteurs le long de l’itinéraire, comme dans un problème de plus court chemin ordinaire. Le nouveau temps est max(t, height), et non t + height.
Utiliser la récursion pour le remplissage par diffusion. Un itinéraire sinueux peut compter des milliers de cases, ce qui dépasse la limite de Python de 1 000 appels imbriqués.
Se déplacer en diagonale. Tu ne peux nager que vers une case qui partage un côté avec la tienne.

Questions fréquentes4

Quelle est la complexité temporelle de Swim in Rising Water ?

O(n² log n) avec l'algorithme de Dijkstra : chacune des n² cellules est insérée puis extraite du tas au plus une fois, celui-ci contenant jusqu'à n² éléments. La recherche dichotomique du niveau de l'eau a la même complexité, avec environ log2(n²) remplissages par propagation de O(n²) chacun. Les deux utilisent O(n²) mémoire pour les marques de visite et le tas ou la pile.

Pourquoi l’algorithme de Dijkstra fonctionne-t-il lorsque le coût est celui de la cellule la plus élevée ?

Dijkstra nécessite une propriété : prolonger un itinéraire ne réduit jamais son coût. Ici, le nouveau coût est max(t, height), qui n’est jamais inférieur à t, donc cette propriété est vérifiée. C’est pourquoi, dès qu’une cellule quitte le tas pour la première fois, son temps est définitif et tu peux t’arrêter à la cible.

Peut-on résoudre le problème « Can Swim in Rising Water » avec une recherche binaire ?

Oui. La possibilité de traverser au niveau t est fausse pour tous les niveaux inférieurs à la réponse, et vraie à partir de la réponse. Une recherche binaire sur t, avec un remplissage par propagation comme test, trouve la réponse en environ log2(n²) tests : 14 pour une grille de 100 × 100.

Peut-on résoudre « Swim in Rising Water » avec union-find ?

Oui. Ouvrez les cellules par ordre de hauteur, reliez chaque nouvelle cellule à ses voisines ouvertes et arrêtez-vous dès que le coin supérieur gauche et le coin inférieur droit appartiennent au même ensemble. La hauteur de la dernière cellule ouverte est la réponse. Puisque la grille contient une fois chaque valeur de 0 à n²-1, une table associant chaque hauteur à une cellule donne l’ordre d’ouverture sans tri.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

grid = [[0, 2], [3, 1]]

Attendu

Swim in Rising Water

Fonction

Contraintes

Exemples

Indices

Solution

Faites monter l’eau une étape à la fois

Recherche binaire sur le niveau de l’eau

Dijkstra sur la cellule la plus haute du parcours

Pièges et cas limites

Questions fréquentes4

Problèmes similaires