Swim in Rising Water

Q: Какова временная сложность алгоритма Swim in Rising Water?

O(n² log n) с алгоритмом Дейкстры: каждая из n² ячеек добавляется в кучу и извлекается из неё не более одного раза; размер кучи составляет до n² элементов. Двоичный поиск по уровню воды имеет ту же оценку: примерно log2(n²) обходов затопленных областей, каждый за O(n²). Оба алгоритма используют O(n²) памяти для отметок посещённых ячеек и кучи или стека.

Q: Почему алгоритм Дейкстры работает, если стоимость равна значению самой дорогой клетки?

Алгоритму Дейкстры требуется одно свойство: продолжение маршрута никогда не снижает его стоимость. Здесь новая стоимость — max(t, height) , которая никогда не бывает меньше t , поэтому это свойство выполняется. Именно поэтому время клетки становится окончательным при её первом извлечении из кучи, и можно остановиться, достигнув целевой клетки.

Q: Можно ли решить задачу Can Swim in Rising Water с помощью бинарного поиска?

Да. Возможность перебраться на уровне t отсутствует для всех уровней ниже ответа и есть начиная с ответа. Бинарный поиск по t с заливкой в качестве проверки находит ответ примерно за log2(n²) проверок: 14 для сетки 100 × 100.

Q: Может ли структура «система непересекающихся множеств» решить задачу Swim in Rising Water?

Да. Открывайте клетки в порядке возрастания высоты, объединяйте каждую новую клетку с её открытыми соседями и останавливайтесь, как только верхняя левая и нижняя правая клетки окажутся в одном множестве. Высота клетки, которую вы открыли последней, и есть ответ. Поскольку в сетке каждое значение от 0 до n²-1 встречается один раз, таблица, связывающая высоту с клеткой, задаёт порядок открытия без сортировки.

СложноКратчайшие пути Куча Бинарный поиск

+10

Дана сетка высот размером n × n, содержащая каждое число от 0 до n²-1 ровно один раз, в виде списка строк. Дождь начинается в момент времени 0, и в момент времени t уровень воды везде равен t, поэтому каждая клетка высотой не более t находится под водой. Вы начинаете в верхней левой клетке. Вы можете переплыть из клетки в соседнюю по стороне, если обе находятся под водой; плавание не занимает времени. Верните самое раннее время, когда вы сможете оказаться в нижней правой клетке.

Функция

swimInWater(grid: integer-2d-array) → integer

gridinteger-2d-array: высоты в виде списка из n строк по n чисел
Возвращаетinteger: самое раннее время, когда вы можете добраться до ячейки в правом нижнем углу

Ограничения

n == grid.length == grid[i].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
Каждое значение от 0 до n²-1 встречается ровно один раз.

Примеры

Ввод: grid = [[0, 2], [3, 1]]
Вывод: 2
Пояснение: Через верхнюю правую ячейку маршрут проходит через 0, 2, 1, а его наивысшая ячейка — 2. Через нижнюю левую ячейку маршрут проходит через 0, 3, 1, а его наивысшая ячейка — 3. В момент времени 2 первый маршрут находится под водой, поэтому ответ — 2.

+13 скрытых тестов при отправке

Дополнительный вопрос

Если высоты могут повторяться и достигать 10^9, какой из ваших подходов по-прежнему работает без изменений и по чему вы бы выполняли бинарный поиск?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Время, необходимое маршруту, определяется его самой высокой ячейкой, потому что вода должна покрыть каждую ячейку, через которую вы проходите. Значит, задача — найти маршрут между углами, у которого самая высокая ячейка как можно ниже: кратчайший путь, стоимость которого определяется максимумом, а не суммой. Можно поднимать уровень воды на один шаг за раз и проверять его, выполнить бинарный поиск по уровню воды с той же проверкой или запустить алгоритм Дейкстры, считая стоимостью самую высокую ячейку.

Поднимайте уровень воды по одному шагу за раз

Верно, но не успевает на самых больших тестах

Идея

Зафиксируем уровень воды t. Досягаемы те клетки, высота которых не превышает t и которые соединены со стартовой клеткой через такие клетки. Их можно найти одним поиском с заливкой из верхнего левого угла: добавить стартовую клетку, извлечь клетку и добавить каждого непосещённого соседа высотой не выше t. Если нижний правый угол посещён, уровня t достаточно.

Ответ — наименьшее значение t, при котором поиск с заливкой добирается до цели. Оно не может быть меньше высоты более высокого угла, max(grid[0][0], grid[n-1][n-1]), поскольку оба угла должны оказаться под водой. Начинаем с этого значения и увеличиваем его на 1, пока поиск не завершится успешно. Первый подходящий уровень и есть ответ, потому что поднимающаяся вода только открывает клетки и никогда их не закрывает: если некоторый уровень подходит, то подходят и все последующие.

Каждая проверка требует O(n²), а уровень воды может подняться почти n² раз, прежде чем поиск доберётся до цели. На сетке размером 100 × 100 это до 10^4 уровней × 10^4 клеток, то есть около 10^8 посещений клеток. В больших тестах в углах стоят 0 и 1, а ответы лежат в диапазоне от 4,950 до 9,998, поэтому до получения ответа выполняются тысячи полных поисков с заливкой.

Алгоритм

Установи 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

Бинарный поиск по уровню воды

Идея

У теста из первого подхода полезная форма. Он даёт отрицательный результат для всех уровней ниже ответа и положительный — для самого ответа и всех уровней выше. Бинарный поиск находит ответ на вопрос, допускающий ответы «да» или «нет» и меняющий ответ ровно один раз с «нет» на «да», за логарифмическое число попыток.

Выполняйте поиск между lo, верхним углом, и hi = n²-1, самой высокой ячейкой, при котором вся сетка находится под водой и тест обязательно должен пройти. Проверьте средний уровень. Если вы добрались до цели, ответ не выше mid, поэтому задайте hi = mid; если нет, ответ выше mid, поэтому задайте lo = mid + 1. Когда границы совпадут, этот уровень и будет ответом.

В примере с сеткой 5 × 5 lo = 6 и hi = 24. Уровень 15 не подходит, потому что верхняя область замкнута, поэтому lo = 16. Уровни 20, 18, 17 и 16 подходят, постепенно снижая hi до 16; поиск завершается на уровне 16 после пяти обходов в глубину.

В сетке 100 × 100 есть 10^4 уровней, поэтому решение определяется примерно за 14 проверок, каждая из которых занимает O(n²): около 1.4 × 10^5 посещений ячеек вместо 10^8. Оставьте обход в глубину итеративным. Один из больших тестов — извилистый коридор длиной около 5,000 ячеек, гораздо длиннее лимита Python в 1,000 вложенных вызовов.

Алгоритм

Установи 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

Алгоритм Дейкстры на самой высокой клетке маршрута

Идея

Рассматривайте сетку как граф и назначьте каждому маршруту стоимость: высоту самой высокой клетки, а не сумму высот клеток на пути. Алгоритм Дейкстры по-прежнему работает с такой стоимостью, потому что добавление шага к маршруту никогда не делает его дешевле. Стоимость более длинного маршрута равна max(old cost, new height) и никогда не бывает меньше прежней стоимости — именно это свойство и нужно алгоритму Дейкстры.

Поддерживайте мин-кучу клеток, упорядоченных по времени — высоте самой высокой клетки на лучшем найденном до них маршруте. Начните с верхней левой клетки, время для которой равно grid[0][0]. Извлеките клетку с наименьшим временем t; каждой ещё не посещённой соседней клетке назначьте время max(t, its height). Когда нижняя правая клетка будет извлечена из кучи, её время и будет ответом.

Клетку можно пометить как посещённую при первом добавлении в кучу. Клетки извлекаются из кучи в порядке времени, поэтому первой до соседа доберётся клетка с наименьшим временем среди всех клеток, которые когда-либо смогут до него добраться, и рассчитанное по этому маршруту время для соседа будет наилучшим возможным. Более поздний маршрут приведёт к нему не раньше. Поэтому каждая клетка попадает в кучу один раз — со своим окончательным временем.

Это и есть подъём воды, шаг за шагом. В куче хранятся клетки на границе доступной области, а извлечение клетки с наименьшей высотой означает, что вода поднялась ровно настолько, чтобы можно было на неё наступить. В примере 5 × 5 клетки извлекаются в порядке 0, 1, 2, 3, 4, 5, а затем — проход с высотой 16. После этого каждая клетка на обходном пути получит время 16, и нижняя правая клетка будет извлечена из кучи со временем 16, раньше любой клетки с большей высотой.

Каждая из n² клеток добавляется в кучу и извлекается из неё не более одного раза, затрачивая O(log n) на каждую операцию, поэтому время работы составляет O(n² log n), а поиск прекращается, как только целевая клетка будет извлечена.

Алгоритм

Отметь верхнюю левую ячейку как посещённую и добавь её в очередь с временем 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]. Для [[3, 0], [1, 2]] ответ равен 3.
Игнорирование высоты целевой клетки. Нижний правый угол тоже должен оказаться под водой, поэтому ответ не меньше grid[n-1][n-1].
Жадное перемещение к соседу с наименьшей высотой. Лучший маршрут может вести вверх, к проходу, а затем обходить длинным путём, как в примере с сеткой 5 × 5. Найти его позволяет только поиск по всему краю достигнутой области.
Сложение высот вдоль маршрута, как при обычном поиске кратчайшего пути. Новое время — это max(t, height), а не t + height.
Использование рекурсии для заполнения области. Извилистый маршрут может состоять из тысяч клеток, что превышает лимит Python в 1 000 вложенных вызовов.
Перемещение по диагонали. Плыть можно только в клетку, которая имеет с вашей общую сторону.

Частые вопросы4

Какова временная сложность алгоритма Swim in Rising Water?

O(n² log n) с алгоритмом Дейкстры: каждая из n² ячеек добавляется в кучу и извлекается из неё не более одного раза; размер кучи составляет до n² элементов. Двоичный поиск по уровню воды имеет ту же оценку: примерно log2(n²) обходов затопленных областей, каждый за O(n²). Оба алгоритма используют O(n²) памяти для отметок посещённых ячеек и кучи или стека.

Почему алгоритм Дейкстры работает, если стоимость равна значению самой дорогой клетки?

Алгоритму Дейкстры требуется одно свойство: продолжение маршрута никогда не снижает его стоимость. Здесь новая стоимость — max(t, height), которая никогда не бывает меньше t, поэтому это свойство выполняется. Именно поэтому время клетки становится окончательным при её первом извлечении из кучи, и можно остановиться, достигнув целевой клетки.

Можно ли решить задачу Can Swim in Rising Water с помощью бинарного поиска?

Да. Возможность перебраться на уровне t отсутствует для всех уровней ниже ответа и есть начиная с ответа. Бинарный поиск по t с заливкой в качестве проверки находит ответ примерно за log2(n²) проверок: 14 для сетки 100 × 100.

Может ли структура «система непересекающихся множеств» решить задачу Swim in Rising Water?

Да. Открывайте клетки в порядке возрастания высоты, объединяйте каждую новую клетку с её открытыми соседями и останавливайтесь, как только верхняя левая и нижняя правая клетки окажутся в одном множестве. Высота клетки, которую вы открыли последней, и есть ответ. Поскольку в сетке каждое значение от 0 до n²-1 встречается один раз, таблица, связывающая высоту с клеткой, задаёт порядок открытия без сортировки.

Python

def swimInWater(grid):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

grid = [[0, 2], [3, 1]]

Ожидается

Swim in Rising Water

Функция

Ограничения

Примеры

Подсказки

Решение

Поднимайте уровень воды по одному шагу за раз

Бинарный поиск по уровню воды

Алгоритм Дейкстры на самой высокой клетке маршрута

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи