Swim in Rising Water
Você recebe uma grade n × n de alturas que contém todos os números de 0 a n²-1 exatamente uma vez, como uma lista de linhas. A chuva começa no instante 0 e, no instante t, a água fica na altura t em toda parte, então toda célula com altura menor ou igual a t fica submersa. Você começa na célula do canto superior esquerdo. Você pode nadar de uma célula para outra que compartilhe um lado com ela quando ambas estiverem submersas, e nadar não leva tempo. Retorne o primeiro instante em que você pode chegar à célula do canto inferior direito.
Função
- gridinteger-2d-array
- as alturas, como uma lista de n linhas com n números
- Retornainteger
- o momento mais cedo em que você pode chegar à célula do canto inferior direito
Restrições
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Cada valor de 0 a
n²-1aparece exatamente uma vez.
Exemplos
- Entrada
- grid = [[0, 2], [3, 1]]
- Saída
- 2
- Explicação
- Pela célula superior direita, a rota é 0, 2, 1, e sua célula mais alta é 2. Pela célula inferior esquerda, a rota é 0, 3, 1, com a célula mais alta sendo 3. No tempo 2, a primeira rota está submersa, então a resposta é 2.
- 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]]
- Saída
- 16
- Explicação
- No instante 15, você pode chegar à fileira de cima e ao 5 abaixo do seu fim, mas todos os caminhos para sair dessa área passam por 16 ou mais. Seguindo direto para baixo pelo lado direito, você encontra 16 e depois 20. Virando à esquerda em 16 e contornando por 15, 14, 13, 12, 11 e voltando pela fileira de baixo, você nunca ultrapassa 16, então a resposta é 16.
- Entrada
- grid = [[3, 0], [1, 2]]
- Saída
- 3
- Explicação
- A célula inicial tem altura 3, então você não pode estar nela nem sair dela antes do tempo 3. Até lá, toda a grade estará debaixo d'água.
+13 testes ocultos ao enviar
Para ir além
Se as alturas pudessem se repetir e chegar a 10^9, qual das suas abordagens ainda funcionaria sem alterações, e sobre o que você faria uma busca binária?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Suponha que você saiba o nível da água
t. Você consegue dizer se existe um caminho para atravessar? Como essa resposta muda à medida quetaumenta?Uma rota precisa que a água cubra todas as células por onde passa, então o tempo necessário para uma rota é determinado pela célula mais alta dela. Você quer a rota entre os cantos cuja célula mais alta seja a mais baixa possível.
Faça uma busca binária em
tusando um preenchimento por inundação como teste, ou execute o algoritmo de Dijkstra com uma fila de prioridade mínima, em que o tempo de uma célula é o maior entre o tempo com que você chegou e a altura da própria célula. Pare quando a célula inferior direita sair da fila.
Solução
O tempo de que uma rota precisa é determinado por sua célula mais alta, pois a água precisa cobrir cada célula pela qual você passa. Portanto, a tarefa é encontrar a rota entre os cantos cuja célula mais alta seja a mais baixa possível: um caminho mínimo em que o custo do caminho é seu valor máximo, não a soma. Você pode elevar o nível da água um passo de cada vez e testar, fazer uma busca binária no nível da água usando o mesmo teste ou executar o algoritmo de Dijkstra considerando a célula mais alta como custo.
Eleve o nível da água um passo de cada vez
Correta, mas não termina nos maiores testes
Intuição
Fixe um nível de água t. As células que você pode alcançar são aquelas com altura menor ou igual a t que se conectam ao início através dessas células. Uma busca em largura a partir do canto superior esquerdo as encontra: adicione o início, remova uma célula e adicione cada vizinha ainda não visitada com altura menor ou igual a t. Se o canto inferior direito for visitado, o nível t é suficiente.
A resposta é o menor t para o qual a busca em largura consegue chegar ao destino. Ele não pode ser menor que o maior valor nos cantos, max(grid[0][0], grid[n-1][n-1]), pois ambos os cantos precisam ficar submersos. Comece por esse valor e adicione 1 até que a busca seja bem-sucedida. O primeiro nível que funciona é a resposta, porque a água subindo apenas abre células, nunca fecha nenhuma: um nível que funciona continuará funcionando.
Cada teste custa O(n²), e a água pode subir quase n² vezes antes de a busca conseguir chegar ao destino. Em uma grade de 100 × 100, isso representa até 10^4 níveis × 10^4 células, cerca de 10^8 visitas a células. Nos testes grandes, os cantos contêm 0 e 1, e as respostas ficam entre 4.950 e 9.998, então milhares de buscas em largura completas são executadas antes de a resposta aparecer.
Algoritmo
- Defina
tcomo a maior das alturas dos dois cantos. - Faça um preenchimento por inundação a partir do canto superior esquerdo, passando pelas células com altura menor ou igual a
t, usando uma pilha explícita e uma marca de visitado por célula. - Se o preenchimento alcançar o canto inferior direito, retorne
t. - Caso contrário, some 1 a
te faça o preenchimento novamente.
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 tBusca binária no nível da água
Intuição
O teste da primeira abordagem tem um formato útil. Ele falha para todos os níveis abaixo da resposta e tem sucesso para todos os níveis a partir da resposta. Uma pergunta de sim ou não que muda uma vez, de não para sim, é o que a busca binária encontra em um número logarítmico de tentativas.
Pesquise entre lo, o canto mais alto, e hi = n²-1, a célula mais alta, onde toda a grade está sob a água e o teste deve ter sucesso. Teste o nível do meio. Se você conseguir passar, a resposta é no máximo mid, então defina hi = mid; caso contrário, ela está acima de mid, então defina lo = mid + 1. Quando os dois se encontram, esse nível é a resposta.
No exemplo de 5 × 5, lo = 6 e hi = 24. O nível 15 falha, porque a área superior está bloqueada, então lo = 16. Os níveis 20, 18, 17 e 16 têm sucesso, reduzindo hi até 16, e a busca termina em 16 após cinco preenchimentos por inundação.
Uma grade de 100 × 100 tem 10^4 níveis, então cerca de 14 testes são suficientes para decidir, cada um O(n²): cerca de 1.4 × 10^5 visitas a células em vez de 10^8. Mantenha o preenchimento por inundação iterativo. Um teste grande consiste em um corredor sinuoso de cerca de 5,000 células, muito mais profundo do que o limite de 1,000 chamadas aninhadas do Python.
Algoritmo
- Defina
locomo a altura do canto mais alto ehicomon²-1. - Enquanto
lo < hi, calculemid = (lo + hi) / 2, arredondado para baixo. - Faça o preenchimento por inundação no nível
mid. Se chegar ao canto inferior direito, definahi = mid; caso contrário, definalo = mid + 1. - Retorne
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 na célula mais alta da rota
Intuição
Considere a grade como um grafo e atribua a cada rota um custo: sua célula mais alta, não a soma de seus passos. O algoritmo de Dijkstra ainda funciona com esse custo, porque estender uma rota nunca a torna mais barata. O custo da rota mais longa é max(old cost, new height), nunca menor que o custo anterior, e essa é a propriedade de que Dijkstra precisa.
Mantenha um min-heap de células, indexado pelo tempo de cada uma: a célula mais alta na melhor rota encontrada até ela. Comece pelo canto superior esquerdo, no tempo grid[0][0]. Remova a célula com o menor tempo t; cada vizinha que você ainda não visitou recebe o tempo max(t, its height). Quando o canto inferior direito sair do heap, seu tempo será a resposta.
Você pode marcar uma célula como visitada na primeira vez que a inserir. As células saem do heap em ordem de tempo, então a primeira célula a alcançar uma vizinha tem o menor tempo entre todas as células que chegarão até ela, e o tempo dessa vizinha a partir dela é o melhor possível. Uma rota posterior chega com um tempo pelo menos tão grande. Assim, cada célula entra no heap uma vez, com seu tempo final.
É assim que a água sobe, passo a passo. O heap contém a borda da área que você consegue alcançar, e remover sua célula mais baixa é deixar a água subir exatamente o necessário para chegar até ela. No exemplo de 5 × 5, as remoções seguem a ordem 0, 1, 2, 3, 4, 5, depois o portão em 16. Depois disso, cada célula no caminho ao redor recebe o tempo 16, e o canto inferior direito sai do heap com tempo 16 antes de qualquer célula mais alta.
Cada uma das n² células é inserida e removida no máximo uma vez, com custo O(log n) por operação, então o tempo é O(n² log n), e a busca para assim que o destino é removido.
Algoritmo
- Marque o canto superior esquerdo como visitado e coloque-o na fila de prioridade com o tempo
grid[0][0]. - Remova a célula com o menor tempo
t. Se ela for o canto inferior direito, retornet. - Para cada vizinho ainda não visitado, marque-o como visitado e coloque-o na fila com o tempo
max(t, its height). - Repita a partir da etapa 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))
Armadilhas e casos extremos
A maioria das respostas erradas ocorre por esquecer um detalhe, somar os custos em vez de usar o máximo ou se comprometer cedo demais com uma busca.
- Ignorar a altura da própria célula inicial. Você não pode estar no canto superior esquerdo antes que ele fique submerso, então a resposta é pelo menos
grid[0][0]. Com[[3, 0], [1, 2]], a resposta é 3. - Ignorar a altura do destino. O canto inferior direito também precisa ficar submerso, então a resposta é pelo menos
grid[n-1][n-1]. - Seguir gananciosamente para o vizinho mais baixo da célula atual. A melhor rota pode subir até um portão e depois dar uma grande volta, como no exemplo de 5 × 5. Só uma busca por toda a borda da área alcançada encontra essa rota.
- Somar as alturas ao longo da rota, como em um caminho mínimo comum. O novo tempo é
max(t, height), nãot + height. - Usar recursão para preencher a área alagada. Uma rota sinuosa pode ter milhares de células, o que ultrapassa o limite de 1.000 chamadas aninhadas do Python.
- Mover-se na diagonal. Você só pode nadar até uma célula que compartilhe um lado com a sua.
Perguntas frequentes4
Qual é a complexidade de tempo de Swim in Rising Water?
O(n² log n) com o algoritmo de Dijkstra: cada uma das n² células é inserida e removida da heap no máximo uma vez, em uma heap com até n² entradas. A busca binária no nível da água tem o mesmo limite, cerca de log2(n²) preenchimentos por inundação de O(n²) cada. Ambos usam O(n²) de memória para as marcações de visitados e a heap ou pilha.
Por que o algoritmo de Dijkstra funciona quando o custo é o da célula mais alta?
Dijkstra exige uma propriedade: estender uma rota nunca reduz seu custo. Aqui, o novo custo é max(t, height), que nunca é menor que t, então a propriedade é válida. É por isso que, na primeira vez que uma célula sai da fila de prioridade, seu tempo é definitivo e você pode parar ao chegar ao destino.
É possível resolver Can Swim in Rising Water com busca binária?
Sim. A possibilidade de atravessar no nível t é falsa para todos os níveis abaixo da resposta e verdadeira a partir da resposta. A busca binária por t, usando um preenchimento por inundação como teste, encontra a resposta em cerca de log2(n²) testes: 14 para uma grade de 100 × 100.
O union-find pode resolver Swim in Rising Water?
Sim. Abra as células em ordem de altura, una cada célula nova aos seus vizinhos abertos e pare assim que o canto superior esquerdo e o canto inferior direito estiverem no mesmo conjunto. A altura da última célula que você abriu é a resposta. Como a grade contém cada valor de 0 a n²-1 uma única vez, uma tabela que mapeia alturas para células fornece a ordem de abertura sem precisar ordenar.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def swimInWater(grid):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
grid = [[0, 2], [3, 1]]
Esperado
2