Комментарии 10
Что насчёт закрытых полостей типа грот, у которых через дно есть выход на верх? Два сообщающийся сосуда?
У вас получилось за O(N * ln(N)) от числа клеток.
Навскидку, можно сделать за O(N). Стартуем волной алгоритм (поиск в ширину, bfs), исходно добавив в очередь все крайние клетки. Далее от каждой клетки переходим только к тем её непросмотренным соседям, высота которых не меньше самой клетки. Таким образом мы переберем все клетки, с которых вода стечет и они останутся сухими.
После завершения обхода останутся "озера". Каждое озеро обходим по периметру, определяем самую низкую "береговую" точку. Высота этой точки - уровень воды в озере. Заполняем озеро водой (по тому же волновому алгоритму, или какому-то иному алгоритму заливки), считаем глубины. После затопления озера в нем могут остаться "острова" и "полуострова", их обрабатываем аналогично решению всей задачи - bfs от краёв и т.д.
Самый тонкий момент - где держать найденные озера. Для этого потребуется отдельная очередь достигнутых клеток. То есть если на некоторую клетку в ходе bfs вышли с более высокого соседа, эту клетку добавим в вышеупомянутую очередь. Если на эту клетку потом выйдем выйдем с более низкого соседа, клетка идет в bfs и выкидывается из очереди достигнутых. По завершении bfs смотрим очередь достигнутых, то что там осталось - это клетки, принадлежащие озерам.
Тут проблема, что делать с островами и вложенными в них озерами. Вроде такого:
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. Высота в центральной клетке зависит от того, а что там во внешней стене далеко происходит. Это одним обходом по контуру озера никак не записать.
В этом примере внутреннюю стенку из пятерок можно считать принадлежащей к большому озеру, только глубина на этих клетках будет нулевая (и на результат не повлияет). То есть заливка не останавливается на этих клетках.
Если внешнюю 5 заменить на 2, то да, получится остров, и мы с ним работаем точно так же, как со всей картой: берем все крайние клетки острова и по ним начинаем bfs внутрь. Обработав остров, выйдем на маленькое озеро.
Я сформулировал, почему ваш алгоритм не работает: чтобы найти острова, вам надо знать уровень воды. Чтобы найти уровень воды в озере, вам надо знать его границу. Чтобы найти границу, вам надо знать острова, ведь они могут отсекать часть границы.
Простейший пример:
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)). Но все-равно не линия.
Еще можно искать озера от самой низкой клетки границы, сразу останавливаясь на островах. Но тут логарифм вылезет из-за сортировки или кучи.
Еще есть решение и за O(NM+K), где K — максимльно возможное число в массиве.
Во-первых, есть решение за O(NM log(nm)): надо в графе из клеток и "внешности" найти расстояние до всех клеток из внешности с функцией расстояния — "максимальное значение клетки в пути".
В каждой клетке высота столбика будет равна минимуму из максимальных высот по всем путям наружу. Ведь если есть какой-то путь, где самая высокая клетка имеет высоту k, то вода не может быть выше k тут, потому что она по этому пути сможет стечь. Ну и наоборот, если высота воды не может быть выше k тут, то любой квант воды выше k должен как-то стечь наружу по поверхности воды, а значит путь с высотой не больше k точно есть.
С такой функцией расстояния уже можно запускать дейкстру с приоритетной очередью, что и будет O(NM log(NM)). Но можно и соптимизировать это до O(NM + K): поскольку все возможные значения расстояния от 0 до K, то можно хранить K+1 списков вершин с расстояниями до них, вместо приоритетной очереди. При пересчете расстояния до вершины надо ее удалить из одного списка и вставить в другой. А сама Дейкстра реализуется проходом по всем списками и обработки вершин из списка.
Задачка: Сбор дождевой воды 3D