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. No instante t, a água está na altura t em todos os lugares, então toda célula com altura menor ou igual a t fica submersa. Você começa na célula superior esquerda. Você pode nadar, sem gastar tempo, até uma célula que compartilhe um lado com a sua quando ambas estiverem submersas. Retorne o primeiro instante em que você pode estar na célula inferior direita.
Função
- gridinteger-2d-array
- as alturas, como uma lista de n linhas com n números
- Retornainteger
- o menor tempo em que você pode chegar à célula inferior direita
Restrições
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Todos os valores de 0 a
n²-1aparecem 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, com a célula mais alta sendo 2. Pela célula inferior esquerda, é 0, 3, 1, com a célula mais alta sendo 3. No instante 2, a primeira rota está submersa.
- 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ê alcança apenas a fileira de cima e o 5 abaixo do seu fim; todos os caminhos para sair passam por 16 ou mais. Dando a volta de 16 por 15, 14, 13, 12, 11 e pela fileira de baixo, você nunca sobe acima de 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. Nesse momento, toda a grade estará submersa.
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 a 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 uma passagem? Como essa resposta muda à medida quetaumenta?Uma rota precisa que a água cubra todas as células dela, então o tempo necessário para uma rota é determinado pela célula mais alta. 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 heap mínima, em que o tempo de uma célula é o maior entre o tempo com que você chegou até ela e a própria altura dela. Pare quando a célula inferior direita sair da heap.
Solução
Uma rota precisa de tanto tempo quanto a sua célula mais alta, porque a água precisa cobrir todas as células pelas quais você passa. Portanto, encontre a rota entre os cantos cuja célula mais alta seja a mais baixa: um caminho mais curto cujo custo é o máximo, não a soma. Eleve o nível da água passo a passo, faça uma busca binária do nível ou execute o algoritmo de Dijkstra com esse custo.
Eleve a água um nível de cada vez
Correta, mas não termina nos maiores testes
Intuição
Fixe um nível de água t. Um preenchimento por inundação a partir do canto superior esquerdo, passando por células de altura no máximo t, indica se o canto inferior direito pode ser alcançado. Comece com t igual ao valor do canto mais alto, max(grid[0][0], grid[n-1][n-1]), já que os dois cantos precisam estar submersos, e aumente 1 até que o preenchimento consiga chegar ao destino. A elevação da água apenas libera células, então o primeiro nível que funciona é a resposta.
Cada preenchimento custa O(n²), e a água pode subir quase n² vezes: em uma grade de 100 × 100, até 10^4 níveis × 10^4 células, cerca de 10^8 visitas a células.
Algoritmo
- Defina
tcomo a maior das alturas dos dois cantos. - Faça um preenchimento por inundação a partir do canto superior esquerdo, passando por 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 de preenchimento por inundação falha para todos os níveis abaixo da resposta e tem sucesso para todos os níveis a partir da resposta. A busca binária encontra essa mudança, entre o canto mais alto e n²-1, em que toda a grade fica submersa.
No exemplo de 5 × 5, lo = 6 e hi = 24. O nível 15 falha, então lo = 16. Os níveis 20, 18, 17 e 16 têm sucesso, e a busca termina em 16 após cinco preenchimentos.
Uma grade de 100 × 100 tem 10^4 níveis, então cerca de 14 preenchimentos são suficientes para decidir: aproximadamente 1.4 × 10^5 visitas a células, em vez de 10^8.
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 alcançar o 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
Atribua um custo a cada rota: a célula de maior altura nela. O algoritmo de Dijkstra ainda funciona, porque estender uma rota até uma célula de altura h custa max(old cost, h), nunca menos que o custo antigo. Mantenha um min-heap de células ordenadas por esse tempo, começando pelo canto superior esquerdo em grid[0][0]. 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 lhe atribui o menor tempo possível, e cada célula entra no heap uma única vez.
O heap contém a borda da área que você pode alcançar, e cada remoção aumenta o nível da água exatamente o suficiente para chegar até lá. No exemplo 5 × 5, as remoções acontecem nos tempos 0, 1, 2, 3, 4, 5, depois na passagem em 16, e o canto inferior direito sai com 16.
Algoritmo
- Marque o canto superior esquerdo como visitado e coloque-o na fila com o tempo
grid[0][0]. - Retire da fila 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
- Ignorar a altura do próprio canto. A resposta é pelo menos
grid[0][0]egrid[n-1][n-1]: com[[3, 0], [1, 2]], ela é 3. - Avançar sempre para o vizinho mais baixo. A melhor rota pode subir até um portão e depois dar a volta mais longa, como no exemplo de 5 × 5.
- 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 o preenchimento por inundação. Uma rota sinuosa pode ter milhares de células, o que ultrapassa o limite de 1.000 chamadas aninhadas do Python.
Perguntas frequentes3
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. A busca binária no nível da água tem o mesmo limite, cerca de log2(n²) preenchimentos de O(n²) cada. Ambos usam O(n²) de memória.
É possível resolver “Can Swim in Rising Water” com busca binária?
Sim. A possibilidade de atravessar no nível t muda uma vez, de falso para verdadeiro, na resposta. A busca binária em t, usando um preenchimento por inundação como teste, precisa de cerca de log2(n²) preenchimentos, 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 nova célula às suas vizinhas abertas e pare assim que os dois cantos estiverem no mesmo conjunto. A altura da última célula aberta é a resposta. Como cada valor de 0 a n²-1 aparece uma vez, uma tabela que associa alturas a células fornece a ordem sem precisar ordenar.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def swimInWater(grid):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
grid = [[0, 2], [3, 1]]
Saída Esperada
2