Последнее время я крепко подсел на LeetCode. Нет ничего лучше, чем с утра после чашки кофе зайти на дейлик, быстро придумать решение, с замиранием сердца нажать Submit иии... Accepted! Настроение улучшается и можно спокойно работать. Но так бывает не всегда. Случается, что решения не видно совсем или удается придумать только брутфорсное решение что для LeetCode равносильно тому, что решения нет. Приходится открывать подсказки, смотреть как решили другие. А после некоторых задач вера в возможности собственного ума может и вовсе пошатнуться.
Вот как раз одну из таких задач я предлагаю вам.
Помните задачу про сбор дождевой воды между стенками гребенки? Так вот здесь все то же самое, но только уже в трех измерениях.
Дана матрица высот размера m x n, нужно подсчитать количество воды, которая в ней осталась после дождя. Размеры матрицы могут быть: 1 <= m, n <= 200, высота элемента: 0 <= matrix[n][m] <= 2 * 10^4
Прежде чем смотреть решение попробуйте решить эту задачу самостоятельно. Протестировать можно здесь.
Решение:
Hidden text
Очевидно, что каждый элемент может содержать какое-то количество воды или не содержать воды и быть частью границы одного или нескольких резервуаров с водой.
Также очевидно, что внешние элементы не могут содержать воды, так как она с них будет сливаться, а следовательно они являются границами.
Теперь нужно понять, что если с элементом, который мы определили как границу, рядом находится элемент большей или равной высоты, то такой элемент не может содержать воды и также становится границей. (рис.1)
Хорошо, а что мы можем сказать в ситуации, когда рядом с границей находится элемент, у которого высота меньше? Посмотрим на рис.2, в желтом прямоугольнике у нас внешний элемент высотой 3 и рядом с ним элемент с высотой 0. Заметим, что высота 3 — это наименьшая высота из внешних элементов. Может ли в элементе 0 быть больше воды чем 3? Не может, так как она будет переливаться через рядом стоящую границу с высотой 3. А может ли в элементе 0 быть меньше воды чем 3? Тоже не может, потому что высота 3 — это наименьшая высота из внешних элементов и вода обязательно задержится каким-нибудь из них.
Продолжим обследование и пройдем один шаг вверх и один шаг направо. (рис. 3) Нам встретился элемент с высотой 1 и элемент с высотой 4. Что мы можем про них сказать? У элемента 1 уровень воды будет на уровне элемента 0, а элемент 4 будет границей. Теперь понятно, что если в процессе обследования по цепочке граничного элемента мы будем находить элементы с высотой меньше, чем у граничного то про них можно смело сказать, что они содержат воду. А если высота обследованных элементов больше или равна граничному, то такие элементы будут сами становиться границами, но мы не будем спешить с их обследованием, нам нужно еще одно рассуждение.
Пока мы обследовали элемент находящейся на внешней границе с минимальной высотой все казалось просто и логично, уровень воды определяется по высоте элемента. А как быть с остальными? Посмотрим на элемент с высотой 4. (рис. 4) Рядом с ним элемент с высотой 0 и мы уже не можем сказать уверенно сколько в нем воды. Это будет зависеть от того соединен ли этот элемент посредством элементов содержащими воду с какими-нибудь другими граничными элементами. И тут нужно понять главное – если элемент 4 соединен водой с другими границами с меньшими высотами, то вся вода на этом пути уже будет посчитана в процессе обследования меньших границ. Нам просто нужно действовать от меньших высот к большим. Если мы будем действовать таким образом, то непременно обойдем все элементы и будем знать наверняка какие элементы граничные, а какие содержат воду и уровень воды в них.
Ну вот, когда мы поняли принцип, можно начинать программировать.
Первое, что нам надо сделать это добавить все крайние элементы в очередь, упорядоченную по возрастанию высоты и отметить где-то их координаты как посещенные.
Для добавления в очередь можно написать функцию двоичного поиска. Если у нас есть, например массив чисел, то, чтобы вставить в него новое число с сохранением упорядоченности необязательно перебирать весь массив. Нужно разбить массив посередине и посмотреть в левой или правой половине продолжать поиски, а потом уже эту половину снова пополам и так далее. В худшем случае количество таких итераций будет равно логарифму числа элементов по основанию 2.
После того как мы добавили задачи начинаем их обрабатывать. Для каждой задачи запускаем волновой алгоритм. Подсчитываем воду во всех элементах меньшей высоты, а элементы большей или равной высоты добавляем в очередь с помощью нашей функции двоичного поиска. И так пока не кончатся задачи в очереди. Всё!
В процессе решения мы задействовали 3 инструмента: очередь с приоритетом, бинарный поиск и волновой алгоритм. Неплохо для одной задачки.
Комментарии (9)
Alexandroppolus
02.12.2022 13:04+1У вас получилось за O(N * ln(N)) от числа клеток.
Навскидку, можно сделать за O(N). Стартуем волной алгоритм (поиск в ширину, bfs), исходно добавив в очередь все крайние клетки. Далее от каждой клетки переходим только к тем её непросмотренным соседям, высота которых не меньше самой клетки. Таким образом мы переберем все клетки, с которых вода стечет и они останутся сухими.
После завершения обхода останутся "озера". Каждое озеро обходим по периметру, определяем самую низкую "береговую" точку. Высота этой точки - уровень воды в озере. Заполняем озеро водой (по тому же волновому алгоритму, или какому-то иному алгоритму заливки), считаем глубины. После затопления озера в нем могут остаться "острова" и "полуострова", их обрабатываем аналогично решению всей задачи - bfs от краёв и т.д.
Самый тонкий момент - где держать найденные озера. Для этого потребуется отдельная очередь достигнутых клеток. То есть если на некоторую клетку в ходе bfs вышли с более высокого соседа, эту клетку добавим в вышеупомянутую очередь. Если на эту клетку потом выйдем выйдем с более низкого соседа, клетка идет в bfs и выкидывается из очереди достигнутых. По завершении bfs смотрим очередь достигнутых, то что там осталось - это клетки, принадлежащие озерам.
wataru
02.12.2022 13:38Тут проблема, что делать с островами и вложенными в них озерами. Вроде такого:
6 6 6 6 6 6 6 5 1 1 1 1 1 6 6 1 5 5 5 1 6 6 1 5 1 5 1 6 6 1 5 5 5 1 6 6 1 1 1 1 1 6 6 6 6 6 6 6 6Тут 2 озера. Но, с другой стороны, если одну 5 в стене слева заменить на 6, то озеро остается одним. А если эту 5 заменить на 2, то высота в центральной клетке останется 5. Высота в центральной клетке зависит от того, а что там во внешней стене далеко происходит. Это одним обходом по контуру озера никак не записать.
Alexandroppolus
02.12.2022 14:05В этом примере внутреннюю стенку из пятерок можно считать принадлежащей к большому озеру, только глубина на этих клетках будет нулевая (и на результат не повлияет). То есть заливка не останавливается на этих клетках.
Если внешнюю 5 заменить на 2, то да, получится остров, и мы с ним работаем точно так же, как со всей картой: берем все крайние клетки острова и по ним начинаем bfs внутрь. Обработав остров, выйдем на маленькое озеро.
wataru
03.12.2022 11:17Я сформулировал, почему ваш алгоритм не работает: чтобы найти острова, вам надо знать уровень воды. Чтобы найти уровень воды в озере, вам надо знать его границу. Чтобы найти границу, вам надо знать острова, ведь они могут отсекать часть границы.
Простейший пример:
9 9 9 9 9 3 1 5 1 4 9 9 9 9 9Если вы предлагаете тут сначала найти озеро из трех внутренних клеток, потом заполнить его от 3, и считать все правое островом, то такой подход будет работать не за линию, а за квадрат. Ведь секций, как выше, можно сделать O(N). Первая обработается 1 раз, вторая - 2, последняя - O(N). Конкретно в этой задаче, где есть ограничения на высоту и ширину, а не на общую площадь поля, это будет O(N sqrt(N)). Но все-равно не линия.
Еще можно искать озера от самой низкой клетки границы, сразу останавливаясь на островах. Но тут логарифм вылезет из-за сортировки или кучи.
Alexandroppolus
04.12.2022 14:43Да, убойный контрпример. Понял идею. Похоже, тут таки не ускорить n*ln(n) для общего случая...
wataru
02.12.2022 13:34Еще есть решение и за O(NM+K), где K — максимльно возможное число в массиве.
Во-первых, есть решение за O(NM log(nm)): надо в графе из клеток и "внешности" найти расстояние до всех клеток из внешности с функцией расстояния — "максимальное значение клетки в пути".
ДоказательствоВ каждой клетке высота столбика будет равна минимуму из максимальных высот по всем путям наружу. Ведь если есть какой-то путь, где самая высокая клетка имеет высоту k, то вода не может быть выше k тут, потому что она по этому пути сможет стечь. Ну и наоборот, если высота воды не может быть выше k тут, то любой квант воды выше k должен как-то стечь наружу по поверхности воды, а значит путь с высотой не больше k точно есть.
С такой функцией расстояния уже можно запускать дейкстру с приоритетной очередью, что и будет O(NM log(NM)). Но можно и соптимизировать это до O(NM + K): поскольку все возможные значения расстояния от 0 до K, то можно хранить K+1 списков вершин с расстояниями до них, вместо приоритетной очереди. При пересчете расстояния до вершины надо ее удалить из одного списка и вставить в другой. А сама Дейкстра реализуется проходом по всем списками и обработки вершин из списка.
VaalKIA
Что насчёт закрытых полостей типа грот, у которых через дно есть выход на верх? Два сообщающийся сосуда?
Ultrik Автор
Таких конфигураций в этой задаче быть не может. У нас по условию двумерный массив высот(столбиков), в отдельном столбике не может быть пустых мест(пропусков).
dyanishev
если исходные данные задачи - карта высот, то там физически не может быть полостей и гротов.