Swim in Rising Water
Тебе дана сетка высот размером n × n, в которой каждое число от 0 до n²-1 встречается ровно один раз. В момент времени t вода везде поднимается до высоты t, поэтому каждая клетка высотой не более t оказывается под водой. Ты начинаешь в верхней левой клетке. Ты можешь мгновенно доплыть до клетки, имеющей с твоей общую сторону, если обе клетки находятся под водой. Верни самое раннее время, когда ты можешь оказаться в нижней правой клетке.
Функция
- gridinteger-2d-array
- высоты в виде списка из n строк по n чисел
- Возвращаетinteger
- самое раннее время, когда ты можешь добраться до ячейки в правом нижнем углу
Ограничения
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Каждое значение от 0 до
n²-1встречается ровно один раз.
Примеры
- Ввод
- grid = [[0, 2], [3, 1]]
- Вывод
- 2
- Пояснение
- Через верхнюю правую ячейку проходит маршрут 0, 2, 1, где наибольшая ячейка — 2. Через нижнюю левую — 0, 3, 1, где наибольшая ячейка — 3. В момент времени 2 первый маршрут оказывается под водой.
- Ввод
- 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]]
- Вывод
- 16
- Пояснение
- В момент времени 15 вы достигаете только верхнего ряда и числа 5 под его концом; любой путь наружу проходит через 16 или большее число. Если идти в обход от 16 через 15, 14, 13, 12, 11 и нижний ряд, значение никогда не поднимается выше 16.
- Ввод
- grid = [[3, 0], [1, 2]]
- Вывод
- 3
- Пояснение
- Начальная ячейка имеет высоту 3, поэтому вы не можете находиться в ней и покинуть её раньше времени 3. К тому моменту вся сетка будет под водой.
Дополнительный вопрос
Если высоты могут повторяться и достигать 10^9, какой из ваших подходов по-прежнему будет работать без изменений и по чему вы будете выполнять бинарный поиск?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Предположим, ты знаешь уровень воды
t. Можешь ли ты определить, существует ли путь? Как меняется ответ по мере увеличенияt?Маршрут требует, чтобы вода покрыла каждую клетку на нём, поэтому время, необходимое для прохождения маршрута, определяется его самой высокой клеткой. Вам нужен маршрут между углами, у которого самая высокая клетка как можно ниже.
Либо выполни бинарный поиск по
t, используя заливку как проверку, либо запусти алгоритм Дейкстры с min-кучей, где время для ячейки — это максимум из времени, с которым ты в неё пришёл, и её собственной высоты. Остановись, когда нижняя правая ячейка будет извлечена из кучи.
Решение
Маршруту требуется столько же времени, сколько нужно, чтобы вода покрыла самую высокую клетку на нём, потому что вода должна покрыть каждую клетку, через которую вы проходите. Поэтому найдите маршрут между углами, у которого самая высокая клетка как можно ниже: кратчайший путь, стоимость которого равна максимуму, а не сумме. Поднимайте уровень воды шаг за шагом, выполните двоичный поиск уровня или запустите алгоритм Дейкстры с такой стоимостью.
Поднимайте уровень воды по одному шагу за раз
Верно, но не успевает на самых больших тестах
Идея
Задайте уровень воды t. Один обход заливкой из верхнего левого угла по клеткам высотой не больше t покажет, достижим ли нижний правый угол. Начните с t, равного высоте более высокого угла, max(grid[0][0], grid[n-1][n-1]), поскольку оба угла должны быть под водой, и увеличивайте его на 1, пока обход не достигнет цели. При подъёме воды открываются только новые клетки, поэтому первый подходящий уровень и будет ответом.
Каждый обход требует O(n²), а уровень воды может подняться почти n² раз: на сетке 100 × 100 — до 10^4 уровней × 10^4 клеток, то есть около 10^8 посещений клеток.
Алгоритм
- Установите
tравным большей из двух высот в углах. - Выполните заливку от верхнего левого угла через ячейки высотой не более
t, используя явный стек и отметку посещения для каждой ячейки. - Если заливка достигает нижнего правого угла, верните
t. - В противном случае увеличьте
tна 1 и выполните заливку снова.
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Бинарный поиск по уровню воды
Идея
Тест заливки завершается неудачей для каждого уровня ниже ответа и успешно проходит для каждого уровня, начиная с ответа. Бинарный поиск находит этот переход между верхним углом и n²-1, где вся сетка находится под водой.
В примере 5 × 5 lo = 6 и hi = 24. Уровень 15 не проходит тест, поэтому lo = 16. Уровни 20, 18, 17 и 16 проходят тест, и поиск завершается на 16 после пяти заливок.
Сетка 100 × 100 имеет 10^4 уровней, поэтому для определения ответа требуется около 14 заливок: примерно 1.4 × 10^5 посещений ячеек вместо 10^8.
Алгоритм
- Установи
loравным высоте более высокого угла, аhi— равнымn²-1. - Пока
lo < hi, возьмиmid = (lo + hi) / 2, округлённое вниз. - Выполни заливку на уровне
mid. Если она достигнет правого нижнего угла, установиhi = mid; в противном случае установиlo = mid + 1. - Верни
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Алгоритм Дейкстры на самой высокой клетке маршрута
Идея
Назначь каждому маршруту стоимость: высоту его самой высокой клетки. Алгоритм Дейкстры по-прежнему работает, потому что при продолжении маршрута до клетки высотой h его стоимость становится max(old cost, h), то есть никогда не становится меньше прежней. Храни клетки в минимальной куче, упорядоченной по этому времени, начиная с верхней левой клетки grid[0][0]. Когда нижняя правая клетка покинет кучу, её время и будет ответом.
Можно пометить клетку как посещённую при первом добавлении в кучу. Клетки покидают кучу в порядке времени, поэтому первая клетка, достигшая соседа, задаёт для него минимальное время из возможных, и каждая клетка попадает в кучу только один раз.
Куча хранит границу области, до которой можно добраться, а каждое извлечение повышает уровень воды ровно настолько, чтобы сделать туда шаг. В примере 5 × 5 клетки извлекаются со значениями 0, 1, 2, 3, 4, 5, затем достигаются ворота на высоте 16, и нижняя правая клетка покидает кучу со значением 16.
Алгоритм
- Отметь верхнюю левую клетку как посещённую и добавь её в очередь с временем
grid[0][0]. - Извлеки клетку с наименьшим временем
t. Если это нижняя правая клетка, верниt. - Для каждого ещё не посещённого соседа отметь его как посещённого и добавь в очередь со временем
max(t, its height). - Повторяй, начиная с шага 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))
Ловушки и крайние случаи
- Не учитывать высоту самой угловой клетки. Ответ не меньше
grid[0][0]иgrid[n-1][n-1]: для[[3, 0], [1, 2]]он равен 3. - Жадно идти к соседу с наименьшей высотой. Лучший маршрут может подняться к проходу, а затем обойти длинным путём, как в примере с сеткой 5 × 5.
- Складывать высоты вдоль маршрута, как при поиске обычного кратчайшего пути. Новое время — это
max(t, height), а неt + height. - Использовать рекурсию для заливки. Извилистый маршрут может состоять из тысяч клеток, что приводит к превышению лимита Python в 1 000 вложенных вызовов.
Частые вопросы3
Какова временная сложность алгоритма Swim in Rising Water?
O(n² log n) с алгоритмом Дейкстры: каждая из n² ячеек добавляется в кучу и извлекается из неё не более одного раза. Двоичный поиск уровня воды имеет такую же сложность: примерно log2(n²) обходов с заливкой, каждый за O(n²). Оба алгоритма используют O(n²) памяти.
Можно ли решить задачу «Плавание в поднимающейся воде» с помощью бинарного поиска?
Да. Возможность перебраться на уровне t меняется один раз: с false на true — в точке ответа. Бинарный поиск по t с заливкой области в качестве проверки требует примерно log2(n²) заливок, 14 для сетки 100 × 100.
Может ли структура union-find решить задачу «Swim in Rising Water»?
Да. Открывайте клетки в порядке возрастания высоты, объединяйте каждую новую клетку с её открытыми соседями и остановитесь, как только два угла окажутся в одном множестве. Высота клетки, которую вы открыли последней, и есть ответ. Поскольку каждое значение от 0 до n²-1 встречается один раз, таблица, сопоставляющая высоту клетке, задаёт порядок без сортировки.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def swimInWater(grid):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
grid = [[0, 2], [3, 1]]
Ожидаемый вывод
2