Swim in Rising Water

Q: ¿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 inserta y se extrae del montículo como máximo una vez, en un montículo de hasta n² elementos. La búsqueda binaria del nivel del agua tiene el mismo límite, aproximadamente log2(n²) recorridos de inundación de O(n²) cada uno. Ambos usan O(n²) de memoria para las marcas de visitado y el montículo o la pila.

Q: ¿Por qué funciona el algoritmo de Dijkstra cuando el costo es el valor de la celda más alta?

Dijkstra necesita una propiedad: ampliar una ruta nunca reduce su coste. Aquí, el nuevo coste es max(t, height) , que nunca es inferior a t , así que se cumple la propiedad. Por eso, la primera vez que una celda sale del montículo, su tiempo es definitivo y puedes detenerte al llegar al objetivo.

Q: ¿Se puede resolver «Can Swim in Rising Water» con búsqueda binaria?

Sí. Si puedes cruzar en el nivel t es falso para todos los niveles inferiores a la respuesta y verdadero desde la respuesta en adelante. La búsqueda binaria sobre t , usando un relleno por inundación como prueba, encuentra la respuesta en aproximadamente log2(n²) pruebas: 14 para una cuadrícula de 100 × 100.

Q: ¿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 la esquina superior izquierda y la esquina inferior derecha estén en el mismo conjunto. La altura de la última celda que abriste es la respuesta. Como la cuadrícula contiene una vez cada valor de 0 a n²-1 , una tabla que asocie cada altura con una celda proporciona el orden de apertura sin ordenar.

DifícilCaminos más cortos Montículo Búsqueda binaria

+10

Recibes una cuadrícula n × n de alturas que contiene todos los números del 0 al n²-1 exactamente una vez, en forma de lista de filas. La lluvia empieza en el instante 0 y, en el instante t, el agua alcanza la altura t en todas partes, así que todas las celdas con altura t o menor están bajo el agua. Empiezas en la celda superior izquierda. Puedes nadar de una celda a otra que comparta un lado con ella cuando ambas estén bajo el agua, y nadar no lleva tiempo. Devuelve el instante más temprano en el que puedes llegar a la celda inferior derecha.

Función

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

gridinteger-2d-array: las alturas, como una lista de n filas de n números
Devuelveinteger: el momento más temprano en que puedes llegar a la celda inferior derecha

Restricciones

n == grid.length == grid[i].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
Cada valor de 0 a n²-1 aparece exactamente una vez.

Ejemplos

Entrada: grid = [[0, 2], [3, 1]]
Salida: 2
Explicación: A través de la celda superior derecha, la ruta es 0, 2, 1, y su celda más alta es 2. A través de 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, así que la respuesta es 2.

+13 pruebas ocultas al enviar

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.

0 de 3 abiertas

Solución

El tiempo que necesita una ruta es el de su celda más alta, porque el agua tiene que cubrir cada celda por la que pasas. Así que la tarea consiste en encontrar la ruta entre las esquinas cuya celda más alta sea lo más baja posible: un camino más corto en el que el costo de un camino es su máximo, no su suma. Puedes subir el nivel del agua de uno en uno y comprobarlo, hacer una búsqueda binaria sobre el nivel del agua usando la misma comprobación o ejecutar el algoritmo de Dijkstra usando la celda más alta como costo.

Eleva el agua un paso a la vez

Correcto, pero no termina con las pruebas más grandes

Intuición

Fija un nivel del agua t. Las celdas a las que puedes llegar son las que tienen una altura como máximo de t y que están conectadas con el inicio a través de dichas celdas. Un recorrido de inundación desde la esquina superior izquierda las encuentra: añade la celda inicial, extrae una celda y añade cada vecina no visitada cuya altura sea como máximo t. Si se visita la esquina inferior derecha, el tiempo t es suficiente.

La respuesta es el menor t para el que el recorrido de inundación logra llegar. No puede ser inferior a la esquina más alta, max(grid[0][0], grid[n-1][n-1]), ya que ambas esquinas deben quedar bajo el agua. Empieza por ese nivel y súmale 1 hasta que el recorrido tenga éxito. El primer nivel que funciona es la respuesta, porque el agua al subir solo habilita celdas y nunca las bloquea: un nivel que funciona seguirá funcionando.

Cada prueba cuesta O(n²), y el agua puede subir casi n² veces antes de que se pueda llegar. En una cuadrícula de 100 × 100, eso supone hasta 10^4 niveles × 10^4 celdas, unos 10^8 recorridos de celdas. En las pruebas grandes, las esquinas contienen 0 y 1, y las respuestas están entre 4,950 y 9,998, así que se ejecutan miles de recorridos de inundación completos antes de encontrar la respuesta.

Algoritmo

Establece t en la mayor de las dos alturas de las esquinas.
Rellena 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 t y vuelve a rellenar.

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

Búsqueda binaria en el nivel del agua

Intuición

La prueba del primer enfoque tiene una forma útil. Falla para todos los niveles inferiores a la respuesta y tiene éxito para todos los niveles desde la respuesta en adelante. Una pregunta de sí o no que cambia una sola vez, de no a sí, es lo que encuentra la búsqueda binaria en un número logarítmico de intentos.

Busca entre lo, la esquina más alta, y hi = n²-1, la celda más alta, donde toda la cuadrícula está bajo el agua y la prueba debe tener éxito. Prueba el nivel medio. Si puedes atravesar, la respuesta es como máximo mid, así que establece hi = mid; si no, está por encima de mid, así que establece lo = mid + 1. Cuando ambos coinciden, ese nivel es la respuesta.

En el ejemplo de 5 × 5, lo = 6 y hi = 24. El nivel 15 falla, porque la zona superior queda aislada, así que lo = 16. Los niveles 20, 18, 17 y 16 tienen éxito, reduciendo hi hasta 16, y la búsqueda termina en 16 después de cinco recorridos de inundación.

Una cuadrícula de 100 × 100 tiene 10^4 niveles, así que unos 14 tests bastan para decidirlo; cada uno es O(n²): alrededor de 1.4 × 10^5 visitas a celdas en lugar de 10^8. Mantén el recorrido de inundación iterativo. Una prueba grande es un corredor sinuoso de unos 5,000 celdas de longitud, mucho más profundo que el límite de Python de 1,000 llamadas anidadas.

Algoritmo

Establece lo en la altura de la esquina más alta y hi en n²-1.
Mientras lo < hi, toma mid = (lo + hi) / 2, redondeado hacia abajo.
Realiza un relleno por inundación en el nivel mid. Si llega a la esquina inferior derecha, establece hi = mid; de lo contrario, establece lo = 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 lo

Dijkstra en la celda más alta de la ruta

Intuición

Considera la cuadrícula como un grafo y asigna un costo a cada ruta: su celda más alta, no la suma de sus pasos. El algoritmo de Dijkstra sigue funcionando con ese costo, porque extender una ruta nunca la hace más barata. El costo de la ruta más larga es max(old cost, new height), nunca menor que el costo anterior, y esa es la única propiedad que necesita Dijkstra.

Mantén un montículo mínimo de celdas ordenadas por su tiempo, la celda más alta de la mejor ruta encontrada hasta ellas. Empieza con la celda superior izquierda en el tiempo grid[0][0]. Extrae la celda con el tiempo más pequeño t; cada vecino que no hayas visto recibe el tiempo max(t, its height). Cuando la celda inferior derecha salga del montículo, su tiempo será la respuesta.

Puedes marcar una celda como visitada la primera vez que la insertes. Las celdas salen del montículo en orden de tiempo, así que la primera celda que llega a un vecino tiene el menor tiempo de todas las celdas que llegarán a él, y el tiempo que le asigna al vecino es el mejor posible. Una ruta posterior llega con un tiempo al menos igual. Así que cada celda entra en el montículo una sola vez, con su tiempo final.

Así es como sube el agua, paso a paso. El montículo contiene el límite de la zona a la que puedes llegar, y extraer su celda más baja es dejar que el agua suba justo lo suficiente para llegar allí. En el ejemplo de 5 × 5, las extracciones son 0, 1, 2, 3, 4, 5, y después la compuerta en 16. A partir de ahí, cada celda del rodeo recibe el tiempo 16, y la celda inferior derecha sale del montículo con el tiempo 16 antes que cualquier celda más alta.

Cada una de las n² celdas se inserta y se extrae como máximo una vez, con un costo de O(log n) cada operación, así que el tiempo es O(n² log n), y la búsqueda se detiene en cuanto se extrae el objetivo.

Algoritmo

Marca la esquina superior izquierda como visitada y añádela con el tiempo grid[0][0].
Extrae la celda con el tiempo más pequeño t. Si es la esquina inferior derecha, devuelve t.
Para cada vecino que aún no se haya visitado, márcalo y añádelo 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

La mayoría de las respuestas incorrectas se deben a olvidar una esquina, sumar un costo en lugar de tomar el máximo o confirmar la búsqueda demasiado pronto.

Ignorar la altura de la celda inicial. No puedes estar en la esquina superior izquierda antes de que quede bajo el agua, así que la respuesta es al menos grid[0][0]. Con [[3, 0], [1, 2]], la respuesta es 3.
Ignorar la altura del destino. La esquina inferior derecha también debe quedar bajo el agua, así que la respuesta es al menos grid[n-1][n-1].
Avanzar de forma codiciosa hacia el vecino más bajo de la celda actual. La mejor ruta puede subir hasta una compuerta y luego dar un largo rodeo, como en el ejemplo de 5 × 5. Solo una búsqueda por todo el borde del área alcanzada permite encontrarla.
Sumar las alturas a lo largo de la ruta, como en un camino más corto convencional. El nuevo tiempo es max(t, height), no t + height.
Usar recursión para el recorrido de inundación. Una ruta sinuosa puede tener miles de celdas, lo que supera el límite de Python de 1.000 llamadas anidadas.
Desplazarse en diagonal. Solo puedes nadar a una celda que comparta un lado con la tuya.

Preguntas frecuentes4

¿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 inserta y se extrae del montículo como máximo una vez, en un montículo de hasta n² elementos. La búsqueda binaria del nivel del agua tiene el mismo límite, aproximadamente log2(n²) recorridos de inundación de O(n²) cada uno. Ambos usan O(n²) de memoria para las marcas de visitado y el montículo o la pila.

¿Por qué funciona el algoritmo de Dijkstra cuando el costo es el valor de la celda más alta?

Dijkstra necesita una propiedad: ampliar una ruta nunca reduce su coste. Aquí, el nuevo coste es max(t, height), que nunca es inferior a t, así que se cumple la propiedad. Por eso, la primera vez que una celda sale del montículo, su tiempo es definitivo y puedes detenerte al llegar al objetivo.

¿Se puede resolver «Can Swim in Rising Water» con búsqueda binaria?

Sí. Si puedes cruzar en el nivel t es falso para todos los niveles inferiores a la respuesta y verdadero desde la respuesta en adelante. La búsqueda binaria sobre t, usando un relleno por inundación como prueba, encuentra la respuesta en aproximadamente log2(n²) pruebas: 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 la esquina superior izquierda y la esquina inferior derecha estén en el mismo conjunto. La altura de la última celda que abriste es la respuesta. Como la cuadrícula contiene una vez cada valor de 0 a n²-1, una tabla que asocie cada altura con una celda proporciona el orden de apertura sin ordenar.

Python

def swimInWater(grid):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Swim in Rising Water

Función

Restricciones

Ejemplos

Pistas

Solución

Eleva el agua un paso a la vez

Búsqueda binaria en el nivel del agua

Dijkstra en la celda más alta de la ruta

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares