2577. Tempo mínimo para visitar uma célula em uma grade

dificuldade: hard

tópicos: Array, pesquisa de largura, gráfico, heap (fila de prioridade), matriz, caminho mais curto

You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].

você está de pé na célula Top-Left da matriz no 0 ^th segundo, e você deve se mover para qualquer célula adjacente nas quatro direções: para cima, para baixo, esquerda e direita. Cada movimento que você faz leva 1 segundo.

retornar

o mínimo tempo necessário para o qual você pode visitar a célula inferior direita da matriz. Se você não puder visitar a célula inferior direita, retorne -1 .

Exemplo 1:

• Input: grid = [[0,1,3,2], [5,1,2,5], [4,3,8,6]
• output: 7
• Explicação: Um dos caminhos que podemos seguir é o seguinte:
  em t = 0, estamos na célula (0,0).
  em t = 1, passamos para a célula (0,1). É possível porque a grade [0] [1]
em t = 2, passamos para a célula (1,1). É possível porque a grade [1] [1] em t = 3, passamos para a célula (1,2). É possível porque a grade [1] [2] em t = 4, passamos para a célula (1,1). É possível porque a grade [1] [1] em t = 5, passamos para a célula (1,2). É possível porque a grade [1] [2] em t = 6, passamos para a célula (1,3). É possível porque a grade [1] [3] em t = 7, passamos para a célula (2,3). É possível porque a grade [2] [3] A hora final é 7. Pode -se mostrar que é o tempo mínimo possível.

Exemplo 2:

• Input: grid = [[0,2,4], [3,2,1], [1,0,4]]
• output: -1
• Explicação: Não há caminho do canto superior esquerdo para a célula inferior direita.

restrições:

m == grid.length
n == grid [i] .Length
2 4 sup> 5
0 sup> 5
grid [0] [0] == 0

Dica:

tente usar algum algoritmo que possa encontrar os caminhos mais curtos em um gráfico.
Considere o caso em que você deve ir e voltar entre duas células da matriz para desbloquear outras células.

Solução:

Podemos aplicar uma versão modificada do algoritmo

dijkstra usando uma fila de prioridade . Esse problema é essencialmente nos pede para encontrar o menor tempo necessário para visitar a célula inferior direita da célula superior esquerda, onde cada movimento tem uma restrição de tempo com base nos valores na grade.

Abordagem:

1. representação gráfica : Trate cada célula na grade como um nó. As bordas são as células adjacentes (para cima, para baixo, esquerda, direita) para as quais você pode se mover.

2. fila de prioridade (min-heap) : use uma fila de prioridade para sempre explorar a célula com o menor tempo necessário. Isso garante que estamos processando as células em ordem dos primeiros tempos que podemos alcançá -las.

3. BFS modificado : Para cada célula, verificaremos se podemos mudar para suas células vizinhas e atualizar o horário em que podemos visitá -las. Se uma célula for visitada posteriormente que a corrente, adicionamos novamente à fila com o novo horário.

4. saída inicial : Quando chegarmos à célula inferior direita, podemos retornar a hora. Se esgotarmos a fila sem alcançá -la, retorne -1.

Vamos implementar esta solução em php:

2577. Tempo mínimo para visitar uma célula em uma grade

Php /** * @param inteiro [] [] $ grid * @return inteiro */ Função Mínimo de tempo ($ grid) { ... ... ... /** * vá para ./solution.php */ } // Exemplo 1 $ grid1 = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]; eco mínimo ($ grid1). Php_eol; // saída: 7 // Exemplo 2 $ grid2 = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; eco mínimo ($ grid2). Php_eol; // saída: -1 ?>

Explicação:

1. fila prioritária :
   O SPLPriorityQueue é usado para garantir que as células com o tempo mínimo sejam processadas primeiro. A prioridade é armazenada como -Time porque o splpriorityQueue do PHP é um max -heap por padrão.
   

2. Traversal :
   A partir da célula superior esquerda (0, 0), o algoritmo processa todas as células acessíveis, considerando o tempo mais antigo que cada um pode ser visitado (max (0, grade [newrow] [newcol] - (tempo 1))).
   

3. Cells visited :
   Uma matriz visitada acompanha as células que já foram processadas para evitar cálculos redundantes e loops infinitos.
   

4. limite e verificação de validade :
   O algoritmo garante que permaneçamos dentro dos limites da grade e processos apenas vizinhos válidos.
   

5. cálculo do tempo :
   Cada movimento leva um segundo e, se a célula exigir a espera (ou seja, grade [newrow] [newcol]> tempo 1), o algoritmo aguarda até a hora necessária.
   

6. EDGE CASE :
   Se a fila estiver esgotada e a célula inferior direita não for alcançada, a função retorna -1.
   

---

Análise de complexidade

1. Time Complexity :

   Cada célula é adicionada à fila de prioridade no máximo uma vez:
   • o (m x n x log (m x n)) , onde Complexidade do espaço
   :
2. O espaço para a fila de prioridade e a matriz visitada é

   o (m x n)

   .
   • Exemplo é executado
   Entrada:

$ grid = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]; eco mínimo ($ grid); // saída: 7

---

Entrada:

$ grid = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; eco mínimo ($ grid); // saída: -1

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

Contato Links

$grid = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid); // Output: -1

Se você achou essa série útil, considere dar o

repositório

uma estrela no github ou compartilhar a postagem em suas redes sociais favoritas?. Seu apoio significaria muito para mim! Se você quiser um conteúdo mais útil como este, fique à vontade para me seguir:

Linkedin

github