2577. Tiempo mínimo para visitar una celda en una cuadrícula

dificultad: duro

temas: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Rath

le dan una cuadrícula de matriz m x n que consiste en no negativo enteros donde la cuadrícula [fila] [col] representa el mínimo tiempo requerido para poder visitar la celda (fila, col), que significa que puede visitar la celda (fila) solo cuando el tiempo es mayor que es mayor que o igual a la grid [fila].

está parado en la celda

top-left de la matriz en la celda 0 th ^{, y debe moverse a} cualquier celda adyacente en las cuatro direcciones: arriba, abajo, izquierda y correcta. Cada movimiento que realice toma 1 segundo. return

el

mínimo tiempo requerido en el que puede visitar la celda inferior derecha de la matriz. Si no puede visitar la celda inferior derecha, entonces regrese -1 .

Ejemplo 1:

Entrada:
• grid = [[0,1,3,2], [5,1,2,5], [4,3,8,6]]
output:
• 7
explicación:
• Una de las rutas que podemos tomar es lo siguiente: at t = 0, estamos en la celda (0,0).
  • en t = 1, nos movemos a la celda (0,1). Es posible porque la cuadrícula [0] [1]
  • en t = 2, nos movemos a la celda (1,1). Es posible porque la cuadrícula [1] [1]
  • en t = 3, nos movemos a la celda (1,2). Es posible porque la cuadrícula [1] [2]
  • en t = 4, nos movemos a la celda (1,1). Es posible porque la cuadrícula [1] [1]
  • en t = 5, nos movemos a la celda (1,2). Es posible porque la cuadrícula [1] [2]
  • en t = 6, nos movemos a la celda (1,3). Es posible porque la cuadrícula [1] [3]
  • en t = 7, nos movemos a la celda (2,3). Es posible porque la cuadrícula [2] [3]
  • La última vez es 7. Se puede demostrar que es el tiempo mínimo posible.

Ejemplo 2:

Entrada:
• grid = [[0,2,4], [3,2,1], [1,0,4]]
output:
• -1
explicación:
• no hay ruta desde la parte superior izquierda a la celda inferior derecha.

restricciones:

m == grid.length

• n == Grid [i] .length
• 2
• 4 sup> 5
• 0 sup> 5
• grid [0] [0] == 0

Pista:

intente usar algún algoritmo que pueda encontrar las rutas más cortas en un gráfico.

1. Considere el caso en el que tiene que ir y venir entre dos celdas de la matriz para desbloquear algunas otras celdas.

Solución:

podemos aplicar una versión modificada de

algorithm de dijkstra

usando una cola de prioridad . Este problema esencialmente nos pide que encontremos el tiempo más corto requerido para visitar la celda inferior derecha desde la celda superior izquierda, donde cada movimiento tiene una restricción de tiempo basada en los valores en la cuadrícula. Acercarse:

1. Representación del gráfico

   : trate cada celda en la cuadrícula como un nodo. Los bordes son las celdas adyacentes (arriba, abajo, izquierda, derecha) a las que puede moverse.

2. priority Queue (min-heap)

   : use una cola de prioridad para explorar siempre la celda con el menor tiempo requerido. Esto asegura que estemos procesando las celdas en orden de tiempo más temprano, podemos llegar a ellas.

3. modificado bfs

   : para cada celda, verificaremos si podemos movernos a sus celdas vecinas y actualizar el tiempo en que podemos visitarlas. Si se visita una celda en un momento posterior que la corriente, la agregamos nuevamente a la cola con la nueva hora.

4. Exit temprano

   : una vez que llegamos a la celda inferior derecha, podemos devolver el tiempo. Si agotamos la cola sin alcanzarlo, return -1.

Implementemos esta solución en php:

2577. Tiempo mínimo para visitar una celda en una cuadrícula

Php /** * @param integer [] [] $ grid * @return entero */ función mínima tiempo ($ grid) { ... ... ... /** * ir a ./solution.php */ } // Ejemplo 1 $ grid1 = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]; Echo mínimo tiempo ($ grid1). Php_eol; // Salida: 7 // Ejemplo 2 $ grid2 = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; Echo mínimo tiempo ($ grid2). Php_eol; // Salida: -1 ?>

1. priority Queue

   : Splpriorityqueue se usa para garantizar que las células con el tiempo mínimo se procesen primero. La prioridad se almacena como -Time porque SplpriorityQueue de PHP es un máximo de Weap de forma predeterminada.
   
   

2. traversal

   : A partir de la celda superior izquierda (0, 0), el algoritmo procesa todas las celdas accesibles, considerando el tiempo más temprano se puede visitar (max (0, cuadrícula [newRow] [newcol] - (tiempo 1))).
   
   

3. Visited Cell

   : Una matriz visitada realiza un seguimiento de las celdas que ya se han procesado para evitar cálculos redundantes y bucles infinitos.
   
   

4. boundary y cheque de validez

   : El algoritmo asegura que nos mantengamos dentro de los límites de la cuadrícula y procese solo vecinos válidos.
   
   

5. tiempo de cálculo

   : Cada movimiento toma un segundo, y si la celda requiere esperar (es decir, cuadrícula [newRow] [newcol]> tiempo 1), el algoritmo espera hasta la hora requerida.
   
   

6. borde caso

   : Si la cola se agota y no se alcanza la celda inferior derecha, la función devuelve -1.
   
   

Análisis de complejidad

---

1. Time Complexity

   :

   cada celda se agrega a la cola de prioridad a máximo una vez:
   • o (m x n x log (m x n)) , donde m [&] n son ​​las dimensiones grid. espacio complejidad :
el espacio para la cola de prioridad y la matriz visitada es

2. o (m x n) .

   • Ejemplo de ejecución
   Aporte:
$ grid = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]; echo mínimo tiempo ($ grid); // Salida: 7

---

Aporte:

$ grid = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; echo mínimo tiempo ($ grid); // Salida: -1

Esta solución es eficiente y funciona bien dentro de las restricciones.

$grid = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid); // Output: 7

Enlaces de contacto

$grid = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid); // Output: 7

Si encontró esta serie útil, considere dar el repositorio

una estrella en GitHub o compartir la publicación en sus redes sociales favoritas. ¡Tu apoyo significaría mucho para mí!

Si desea un contenido más útil como este, no dude en seguirme:

linkedin

github