Swim in Rising Water
On vous donne une grille n × n de hauteurs contenant chaque nombre de 0 à n²-1 exactement une fois. À l’instant t, l’eau atteint partout la hauteur t : toutes les cases de hauteur inférieure ou égale à t sont donc sous l’eau. Vous commencez dans la case en haut à gauche. Vous pouvez rejoindre instantanément à la nage une case qui partage un côté avec la vôtre lorsque les deux cases sont sous l’eau. Retournez le premier instant auquel vous pouvez vous trouver dans la case en bas à droite.
Fonction
- gridinteger-2d-array
- les hauteurs, sous la forme d’une liste de n lignes de n nombres
- Renvoieinteger
- le moment le plus tôt où vous pouvez atteindre la cellule en bas à droite
Contraintes
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Chaque valeur de 0 à
n²-1apparaît exactement une fois.
Exemples
- Entrée
- grid = [[0, 2], [3, 1]]
- Sortie
- 2
- Explication
- En passant par la cellule en haut à droite, le trajet est 0, 2, 1, avec une cellule maximale de 2. En passant par celle en bas à gauche, il est de 0, 3, 1, avec une cellule maximale de 3. Au temps 2, le premier trajet est sous l’eau.
- Entrée
- grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
- Sortie
- 16
- Explication
- Au temps 15, tu atteins seulement la rangée du haut et le 5 en dessous de son extrémité ; toutes les sorties passent par 16 ou plus. En faisant le tour à partir de 16, en passant par 15, 14, 13, 12, 11 et la rangée du bas, on ne dépasse jamais 16.
- Entrée
- grid = [[3, 0], [1, 2]]
- Sortie
- 3
- Explication
- La cellule de départ a une hauteur de 3, donc tu ne peux pas t’y trouver ni la quitter avant le temps 3. À ce moment-là, toute la grille est sous l’eau.
Pour aller plus loin
Si les hauteurs pouvaient se répéter et atteindre 10^9, laquelle de tes approches fonctionnerait encore sans changement, et sur quoi effectuerais-tu une recherche binaire ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Supposons que tu connaisses le niveau de l’eau
t. Peux-tu dire s’il existe un passage ? Comment cette réponse change-t-elle lorsquetaugmente ?Un itinéraire nécessite que l’eau recouvre chaque case qu’il emprunte ; le temps nécessaire à un itinéraire correspond donc à la case la plus élevée qu’il traverse. Tu veux trouver l’itinéraire entre les coins dont la case la plus élevée est aussi basse que possible.
Effectuez soit une recherche dichotomique sur
ten utilisant un remplissage par inondation comme test, soit exécutez l’algorithme de Dijkstra avec un tas min, où le temps associé à une cellule est le plus grand entre le temps auquel vous y êtes arrivé et sa propre hauteur. Arrêtez-vous lorsque la cellule en bas à droite sort du tas.
Solution
Un itinéraire nécessite autant de temps que sa case la plus élevée, car l’eau doit recouvrir chaque case traversée. Trouve donc l’itinéraire entre les coins dont la case la plus élevée est la plus basse : un chemin le plus court dont le coût est le maximum, et non la somme. Fais monter l’eau étape par étape, effectue une recherche dichotomique du niveau ou applique l’algorithme de Dijkstra à ce coût.
Faites monter l’eau d’un cran à la fois
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Fixe un niveau d’eau t. Un remplissage à partir du coin supérieur gauche, en passant par les cellules de hauteur au plus égale à t, te permet de savoir si le coin inférieur droit est accessible. Commence avec t égal à la hauteur du coin le plus élevé, max(grid[0][0], grid[n-1][n-1]), car les deux coins doivent être sous l’eau, puis augmente-le de 1 jusqu’à ce que le remplissage atteigne sa destination. La montée des eaux ne fait qu’ouvrir des cellules : le premier niveau qui fonctionne est donc la réponse.
Chaque remplissage coûte O(n²), et le niveau de l’eau peut monter près de n² fois : sur une grille de 100 × 100, jusqu’à 10^4 niveaux × 10^4 cellules, soit environ 10^8 visites de cellules.
Algorithme
- Définis
tà la plus grande des deux hauteurs des coins. - Effectue un remplissage par propagation depuis le coin supérieur gauche, en passant par les cellules dont la hauteur est au plus
t, à l’aide d’une pile explicite et d’une marque de visite par cellule. - Si le remplissage atteint le coin inférieur droit, renvoie
t. - Sinon, ajoute 1 à
tet effectue à nouveau 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 tRecherche binaire du niveau d’eau
Intuition
Le test de remplissage par propagation échoue pour chaque niveau inférieur à la réponse et réussit pour chaque niveau à partir de la réponse. La recherche binaire trouve ce seuil, entre le coin supérieur et n²-1, où toute la grille est sous l’eau.
Dans l’exemple 5 × 5, lo = 6 et hi = 24. Le niveau 15 échoue, donc lo = 16. Les niveaux 20, 18, 17 et 16 réussissent tous, et la recherche s’arrête à 16 après cinq remplissages.
Une grille de 100 × 100 compte 10^4 niveaux, donc environ 14 remplissages suffisent à déterminer la réponse : autour de 1.4 × 10^5 visites de cellules au lieu de 10^8.
Algorithme
- Définissez
losur la hauteur du coin le plus élevé ethisurn²-1. - Tant que
lo < hi, prenezmid = (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éfinissezhi = mid; sinon, définissezlo = mid + 1. - Renvoyez
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 loDijkstra sur la cellule la plus élevée du parcours
Intuition
Attribue à chaque itinéraire un coût : la hauteur de sa cellule la plus élevée. L’algorithme de Dijkstra fonctionne toujours, car prolonger un itinéraire jusqu’à une cellule de hauteur h coûte max(old cost, h), jamais moins que l’ancien coût. Garde un tas min de cellules, triées selon ce temps, en commençant par la cellule en haut à gauche, à grid[0][0]. Lorsque la cellule en bas à droite quitte le tas, son temps est la réponse.
Tu peux marquer une cellule comme visitée dès que tu l’ajoutes au tas. Les cellules quittent le tas par ordre de temps, donc la première cellule qui atteint une voisine lui donne le plus petit temps possible, et chaque cellule entre une seule fois dans le tas.
Le tas contient le bord de la zone que tu peux atteindre, et chaque extraction fait monter l’eau juste assez pour avancer jusque-là. Dans l’exemple 5 × 5, les extractions donnent 0, 1, 2, 3, 4, 5, puis la porte à 16, et la cellule en bas à droite quitte le tas avec 16.
Algorithme
- Marquez la case en haut à gauche comme visitée et empilez-la avec le temps
grid[0][0]. - Dépilez la cellule ayant le temps
tle plus petit. Si c’est celle en bas à droite, renvoyezt. - Pour chaque voisine qui n’a pas encore été visitée, marquez-la et empilez-la avec le temps
max(t, its height). - Recommencez à 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
- Ignorer la hauteur propre à un coin. La réponse est au moins
grid[0][0]etgrid[n-1][n-1]: avec[[3, 0], [1, 2]], elle vaut 3. - Avancer de façon gloutonne vers le voisin le plus bas. Le meilleur itinéraire peut monter jusqu’à une porte, puis faire un long détour, comme dans l’exemple de 5 × 5.
- Additionner les hauteurs le long de l’itinéraire, comme dans un problème classique de plus court chemin. Le nouveau temps est
max(t, height), et nont + height. - Utiliser la récursivité pour le remplissage par propagation. Un itinéraire sinueux peut compter des milliers de cellules, ce qui dépasse la limite de Python de 1 000 appels imbriqués.
Questions fréquentes3
Quelle est la complexité temporelle de Swim in Rising Water ?
O(n² log n) avec l'algorithme de Dijkstra : chacune des n² cellules est ajoutée puis retirée au plus une fois d'un tas. La recherche dichotomique du niveau de l'eau a la même complexité, avec environ log2(n²) remplissages par inondation de O(n²) chacun. Les deux utilisent O(n²) mémoire.
Peut-on résoudre le problème « Nager dans une eau montante » à l’aide d’une recherche dichotomique ?
Oui. La possibilité de traverser au niveau t bascule une seule fois, de faux à vrai, à la réponse. Une recherche binaire sur t, avec un remplissage par propagation comme test, nécessite environ log2(n²) remplissages, soit 14 pour une grille de 100 × 100.
Union-find peut-il résoudre « Swim in Rising Water » ?
Oui. Ouvrez les cellules par ordre de hauteur, reliez chaque nouvelle cellule à ses voisines ouvertes et arrêtez-vous dès que les deux coins appartiennent au même ensemble. La hauteur de la dernière cellule que vous avez ouverte est la réponse. Comme chaque valeur de 0 à n²-1 apparaît une fois, une table associant chaque hauteur à une cellule donne l’ordre sans tri.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def swimInWater(grid):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
grid = [[0, 2], [3, 1]]
Résultat attendu
2