Swim in Rising Water
Se te da una cuadrícula de alturas n × n que contiene cada número del 0 al n²-1 exactamente una vez. En el instante t, el agua alcanza la altura t en todas partes, así que todas las celdas cuya altura es t o menos están bajo el agua. Empiezas en la celda de la esquina superior izquierda. Puedes nadar, sin que transcurra tiempo, hasta una celda que comparta un lado con la tuya cuando ambas estén bajo el agua. Devuelve el primer instante en que puedes estar en la celda de la esquina inferior derecha.
Función
- gridinteger-2d-array
- las alturas, como una lista de n filas con n números
- Devuelveinteger
- el momento más temprano en que puedes llegar a la celda inferior derecha
Restricciones
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Cada valor de 0 a
n²-1aparece exactamente una vez.
Ejemplos
- Entrada
- grid = [[0, 2], [3, 1]]
- Salida
- 2
- Explicación
- Por la celda superior derecha, la ruta es 0, 2, 1, con la celda más alta en 2. Por la celda inferior izquierda, es 0, 3, 1, con la celda más alta en 3. En el tiempo 2, la primera ruta está bajo el agua.
- Entrada
- 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]]
- Salida
- 16
- Explicación
- En el tiempo 15 solo llegas a la fila superior y al 5 que está debajo de su extremo; todas las salidas pasan por 16 o más. Al rodear desde 16 pasando por 15, 14, 13, 12, 11 y la fila inferior, nunca se supera 16.
- Entrada
- grid = [[3, 0], [1, 2]]
- Salida
- 3
- Explicación
- La celda inicial tiene una altura de 3, así que no puedes estar en ella ni salir de ella antes del tiempo 3. Para entonces, toda la cuadrícula está bajo el agua.
Para ir más allá
Si las alturas pudieran repetirse y llegar a 10^9, ¿cuál de tus enfoques seguiría funcionando sin cambios y sobre qué harías una búsqueda binaria?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Supón que conoces el nivel del agua
t. ¿Puedes determinar si existe un paso? ¿Cómo cambia la respuesta a medida que aumentat?Una ruta necesita que el agua cubra cada celda por la que pasa, así que el tiempo que necesita una ruta es el de su celda más alta. Quieres la ruta entre las esquinas cuya celda más alta sea lo más baja posible.
Haz una búsqueda binaria en
tusando un llenado por inundación como prueba, o ejecuta el algoritmo de Dijkstra con un montículo mínimo, donde el tiempo de una celda es el mayor entre el tiempo con el que llegaste y su propia altura. Detente cuando la celda inferior derecha salga del montículo.
Solución
Una ruta necesita tanto tiempo como su celda más alta, porque el agua tiene que cubrir cada celda por la que pasas. Así que encuentra la ruta entre las esquinas cuya celda más alta sea la más baja: un camino más corto cuyo costo es el máximo, no la suma. Sube el nivel del agua paso a paso, busca el nivel mediante búsqueda binaria o ejecuta el algoritmo de Dijkstra con ese costo.
Sube el nivel del agua paso a paso
Correcto, pero no termina con las pruebas más grandes
Intuición
Fija un nivel de agua t. Un recorrido de inundación desde la esquina superior izquierda, a través de celdas cuya altura es como máximo t, te indica si se puede llegar a la esquina inferior derecha. Empieza t en la esquina más alta, max(grid[0][0], grid[n-1][n-1]), ya que ambas esquinas deben quedar bajo el agua, y súmalo de 1 en 1 hasta que el recorrido logre pasar. El agua creciente solo abre celdas, así que el primer nivel que funciona es la respuesta.
Cada recorrido cuesta O(n²), y el nivel del agua puede subir casi n² veces: en una cuadrícula de 100 × 100, hasta 10^4 niveles × 10^4 celdas, unos 10^8 recorridos de celdas.
Algoritmo
- Establece
tcomo la mayor de las dos alturas de las esquinas. - Realiza un relleno por inundación desde la esquina superior izquierda a través de las celdas cuya altura sea como máximo
t, usando una pila explícita y una marca de visitado por celda. - Si el relleno llega a la esquina inferior derecha, devuelve
t. - De lo contrario, suma 1 a
ty vuelve a realizar el relleno.
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 tBúsqueda binaria en el nivel del agua
Intuición
La prueba de llenado por inundación falla para todos los niveles inferiores a la respuesta y tiene éxito para todos los niveles a partir de la respuesta. La búsqueda binaria encuentra ese cambio, entre la esquina más alta y n²-1, donde toda la cuadrícula queda bajo el agua.
En el ejemplo de 5 × 5, lo = 6 y hi = 24. El nivel 15 falla, así que lo = 16. Los niveles 20, 18, 17 y 16 tienen éxito, y la búsqueda termina en 16 después de cinco llenados.
Una cuadrícula de 100 × 100 tiene 10^4 niveles, así que unos 14 llenados bastan para decidirlo: alrededor de 1.4 × 10^5 visitas a celdas en lugar de 10^8.
Algoritmo
- Establece
loa la altura de la esquina más alta yhian²-1. - Mientras
lo < hi, tomamid = (lo + hi) / 2, redondeado hacia abajo. - Realiza un relleno por inundación al nivel
mid. Si llega a la esquina inferior derecha, establecehi = mid; de lo contrario, establecelo = mid + 1. - Devuelve
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 en la celda más alta de la ruta
Intuición
Asigna a cada ruta un coste: el valor de su celda más alta. El algoritmo de Dijkstra sigue funcionando, porque extender una ruta hasta una celda de altura h cuesta max(old cost, h), nunca menos que el coste anterior. Mantén un montículo mínimo de celdas ordenadas por ese tiempo, empezando por la esquina superior izquierda en grid[0][0]. Cuando la esquina inferior derecha sale del montículo, su tiempo es la respuesta.
Puedes marcar una celda como visitada la primera vez que la insertas. Las celdas salen del montículo en orden de tiempo, así que la primera celda que alcanza a una vecina le asigna el menor tiempo posible, y cada celda entra en el montículo una sola vez.
El montículo contiene el borde de la zona a la que puedes llegar, y cada extracción eleva el agua justo lo suficiente para avanzar hasta allí. En el ejemplo de 5 × 5, las extracciones dan 0, 1, 2, 3, 4, 5, después la compuerta en 16, y la esquina inferior derecha sale con 16.
Algoritmo
- Marca la celda superior izquierda como visitada y añádela con el tiempo
grid[0][0]. - Extrae la celda con el menor tiempo
t. Si es la celda inferior derecha, devuelvet. - Para cada vecina que aún no se haya visitado, márcala y añádela con el tiempo
max(t, its height). - Repite desde el paso 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))
Errores comunes y casos límite
- Ignorar la altura de una esquina. La respuesta es al menos
grid[0][0]ygrid[n-1][n-1]: con[[3, 0], [1, 2]]es 3. - Avanzar de forma codiciosa hacia el vecino más bajo. La mejor ruta puede subir hasta una puerta y después dar un rodeo largo, como en el ejemplo de 5 × 5.
- Sumar las alturas a lo largo de la ruta, como en un camino más corto ordinario. El nuevo tiempo es
max(t, height), not + height. - Usar recursión para el relleno por inundación. Una ruta sinuosa puede tener miles de celdas, lo que supera el límite de Python de 1.000 llamadas anidadas.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Swim in Rising Water?
O(n² log n) con el algoritmo de Dijkstra: cada una de las n² celdas se añade y se extrae del montículo como máximo una vez. La búsqueda binaria del nivel del agua tiene el mismo límite, aproximadamente log2(n²) inundaciones de O(n²) cada una. Ambas usan O(n²) de memoria.
¿Se puede resolver «Can Swim in Rising Water» mediante búsqueda binaria?
Sí. La posibilidad de cruzar al nivel t cambia una vez, de falso a verdadero, en la respuesta. La búsqueda binaria sobre t, usando un relleno por inundación como prueba, requiere aproximadamente log2(n²) rellenos: 14 para una cuadrícula de 100 × 100.
¿Puede union-find resolver Swim in Rising Water?
Sí. Abre las celdas en orden de altura, une cada celda nueva con sus vecinas abiertas y detente en cuanto las dos esquinas estén en el mismo conjunto. La altura de la última celda que abriste es la respuesta. Como cada valor de 0 a n²-1 aparece una vez, una tabla que asocie cada altura con una celda proporciona el orden sin ordenar.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def swimInWater(grid):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
grid = [[0, 2], [3, 1]]
Salida Esperada
2