Задача на поиск луж в матрице

Всем доброго дня.
Есть задача, который день бьюсь, не могу придумать алгоритм.

"Consider a matrix of integers MxN, where each value represents a height
of imaginary landscape. Now, the whole figure is put into the water,
deep enough to cover the highest peak, and is brought back to the light.
Write a program to compute puddles remained in the landscape."

Идеи на сегодняшний момент таковы. Нужно отсортировать по убыванию высоты и послойно "вытаскивать" матрицу из воды. Допустим, максимальная высота 500. Создаем пустую матрицу, идентичную по размерам исходной. Проверяем, где в исходной матрице есть "столбы" с высотой 500, в этом месте новой матрицы ставим 1. Если в текущей точке высота не 500, в новой матрице пишем ноль.

Таким образом, для каждой высоты получим матрицу из нулей и единиц.

Теперь задача сводится к нахождению замкнутых контуров с нулями в новой матрице, это и будут искомые лужи.

Проблема состоит в том, что я не могу подобрать нужный алгоритм для поиска этих самых контуров. Потому что лужа может быть и формы кольца, и лужа в луже в луже... Идей возникает куча, но все они нерабочие. =\

0

Вот картинка, которая может помочь визуализировать задачу.

Миниатюры

 

0

Сообщение от unspoken лужа в луже в луже...

а зачем вы на это внимание обращаете? Вы просто делаете горизонтальный срез на определённой высоте и ищите замкнутые контуры в срезе

0

Сообщение от ProgJ Вы просто делаете горизонтальный срез на определённой высоте

На какой высоте? И как быть с лужами, уровень воды в которых выше данной высоты?

0

Сообщение от ProgJ а зачем вы на это внимание обращаете? Вы просто делаете горизонтальный срез на определённой высоте и ищите замкнутые контуры в срезе

Я про ситуацию, когда лужи и стены образуют собой что-то типа мишени:
Такую ситуацию я простым поиском замкнутых контуров не смогу решить, просто посчитаю самый верхний контур, а те, что внутри него, будут пропущены.

Добавлено через 11 минут

Сообщение от Shamil1 На какой высоте? И как быть с лужами, уровень воды в которых выше данной высоты?

Смысл в том, чтобы опускаться с максимальной высоты до минимальной и отследить, на каком уровне лужа началась (здесь "начало" - ее верхушка, а "конец" - дно лужи) и на каком она закончится. Если уровень воды в луже выше данной высоты - это здорово, лужа глубокая, осталось только найти, на какой глубине она заканчивается. В этом вся соль метода разбиения на отдельные высоты.

Например, у нас есть следующие различные высоты в матрице: 500, 300, 200, 0. Мы начинаем с высоты 500, создаем новую матрицу из 0 и 1 и ищем лужу из нулей. Если для этой высоты мы уже нашли лужу объемом в 2 клетки, то мы точно знаем, что эта лужа сохранится вплоть до уровня 300. Таким образом мы на уровнях с 500 по 300 получаем (500 - 300) * 2 = 400 клеток (пусть будут литры вместо клеток) лужи. Смотрим высоту 300. Допустим, для этой высоты мы нашли лужу в 1 клетку. (Визуально это выглядит как столб высотой в 300 метров среди столбов в 500:
500 500 500 500
500 300 лужа 500
500 500 500 500).
Таким образом на уровнях с 300 по 200 наша лужа имеет объем в 100 литров. Общая лужа 400 + 100 = 500 литров. Смотрим уровень в 200. Допустим, на этом этапе мы ничего не нашли. Значит, итог - лужа в 500 литров с определенными координатами в матрице.

Надеюсь, понятно объяснила.

Добавлено через 4 минуты
На данном этапе успехи таковы. Алгоритм обхода матрицы из 0 и 1 на предмет поиска замкнутого контура из 1 найден (он и на момент создания темы уже был). Алгоритм нахождения нулей и других единиц в этом контуре найден, но еще не реализован (в этом и была загвоздка, собственно). Буду пробовать, надеюсь, получится.

0

Сообщение от unspoken Если уровень воды в луже выше данной высоты - это здорово, лужа глубокая, осталось только найти, на какой глубине она заканчивается.

Глубина лужи не зависит от того, на какой высоте она расположена. Очень мелкая лужа может быть расположена очень высоко.

Добавлено через 2 минуты

Сообщение от unspoken Мы начинаем с высоты 500, создаем новую матрицу из 0 и 1 и ищем лужу из нулей.

Нули на срезе не гарантируют наличие лужи.

0

Сообщение от Shamil1 Глубина лужи не зависит от того, на какой высоте она расположена. Очень мелкая лужа может быть расположена очень высоко.

Все правильно. Это никак не противоречит алгоритму, который я привела.

Добавлено через 52 секунды

Сообщение от Shamil1 Нули на срезе не гарантируют наличие лужи.

Ясное дело! Я же замкнутый контур из единиц ищу специально для того, чтобы точно сказать, что тут лужа точно есть, она не вытекла. Видимо, все-таки не очень понятно излагаю, мой косяк =)

0

Для наличия лужи необходимо и достаточно наличие клетки (или группы клеток одинаковой высоты), все соседи которой имеют большую высоту. Очевидно, что такая клетка (группа клеток) не может быть расположена с краю.

Алгоритм:
Перебираем все клетки
1. Если клетка принадлежит уже найденной луже, переходим к следующей клетке
2. Если клетка не является впадиной (есть более низкий сосед), переходим к следующей клетке
3. Помечаем клетку как лужу и определяем её размеры:
3.1. Находим самую низкую граничащую клетку-кандидат
3.2. Если у кандидата есть более низкий "сухой" сосед, то больше нельзя увеличть лужу
3.3. Если у кандидата есть более низкий сосед, принадлежащий другой луже, то проверяем, можно ли объединить лужи
3.4. Иначе (все соседи кондидата либо выше кандидата, либо принадлежащие данной луже) добавляем кандидата к луже и продолжаем с 3.1.

Добавлено через 3 минуты

Сообщение от unspoken Мы начинаем с высоты 500, создаем новую матрицу из 0 и 1 и ищем лужу из нулей. Если для этой высоты мы уже нашли лужу объемом в 2 клетки, то мы точно знаем, что эта лужа сохранится вплоть до уровня 300.

А зачем Вам искать глубину лужи?
Нашли замкнутый контур из единиц. Все нули внутри него будут лужей.
Перед переходом к следующей высоте заполняем все лужи единицами (чтобы не мешали поиску новых луж).

1

Сообщение от Shamil1 Для наличия лужи необходимо и достаточно наличие клетки (или группы клеток одинаковой высоты), все соседи которой имеют большую высоту.

Таки нет.
Добавлено через 1 минуту

Сообщение от Shamil1 А зачем Вам искать глубину лужи?

В задании явно не сказано, что именно они хотят получить в ответе. Поэтому я пошла от худшего и решила найти и координаты луж, и их глубины. Не знаю, насколько это верное предположение.

0

Сообщение от unspoken Таки нет.

Зато есть единичка - и это и есть та самая клетка, существование которой является необходимым и достаточным условием наличия данной лужи. А двойки относятся к той же луже (не образуют новую лужу).

Сообщение от unspoken Поэтому я пошла от худшего и решила найти и координаты луж, и их глубины.

Можно запоминать для каждой лужи уровень поверхности. Тогда при желании легко можно будет вычислить глубину в любой клетке.

0

Сообщение от Shamil1 Зато есть единичка - и это и есть та самая клетка, существование которой является необходимым и достаточным условием наличия данной лужи

Тогда так:
Добавлено через 33 секунды

Сообщение от Shamil1 Можно запоминать для каждой лужи уровень поверхности

В смысле?

0

Сообщение от unspoken Тогда так:

Я писал "наличие клетки (или группы клеток одинаковой высоты)". В данном случае - группа клеток одинаковой высоты 1.

У каждой лужи есть как минимум один локальный минимум глубины. И каждый локальный минимум глубины принадлежит какой-то луже. Поэтому "Для наличия лужи необходимо и достаточно наличие клетки (или группы клеток одинаковой высоты), все соседи которой имеют большую высоту."

Суть моего алгоритма: мы находим локальный минимум глубины и начинаем "добавлять воду, пока не польётся через край".

Добавлено через 4 минуты

Сообщение от unspoken В смысле?

Например, в Вашем алгоритме:
Мы нашли замкнутый контур из единиц на высоте 500. Все нули внутри этого контура будут лужей (одной или несколькими лужами). Уровень поверхности воды в этой луже будет 500.
Заменяем нолики внутри контура на единички, уменьшаем высоту и опять ищем замкнутый контур.

0

Сообщение от Shamil1 (или группы клеток одинаковой высоты)

Пардон, прохлопала то, что в скобках =)

Можете дать пару пояснений по Вашему алгоритму?

Сообщение от Shamil1 1. Если клетка принадлежит уже найденной луже, переходим к следующей клетке 2. Если клетка не является впадиной (есть более низкий сосед), переходим к следующей клетке 3. Помечаем клетку как лужу и определяем её размеры: 3.1. Находим самую низкую граничащую клетку-кандидат 3.2. Если у кандидата есть более низкий "сухой" сосед, то больше нельзя увеличть лужу 3.3. Если у кандидата есть более низкий сосед, принадлежащий другой луже, то проверяем, можно ли объединить лужи 3.4. Иначе (все соседи кондидата либо выше кандидата, либо принадлежащие данной луже) добавляем кандидата к луже и продолжаем с 3.1.

Откуда у самой низкой клетки-кандидата еще более низкий сосед? И как более низкий сосед лужи может быть "сухим"?

0

Сообщение от unspoken Откуда у самой низкой клетки-кандидата еще более низкий сосед? И как более низкий сосед лужи может быть "сухим"?

Клетка, которая является соседом кандидата, но сама не является кандидатом.
Например, тут:
левая единица - впадина, двойка - кандидат, правая единица - более низкий сосед кандидата
правая единица не принадлежит луже - поэтому она "сухой" сосед

0

Сообщение от Shamil1 правая единица не принадлежит луже - поэтому она "сухой" сосед

Другой вопрос: как мы поймем, что сосед "сухой" или "мокрый", если мы еще не всю матрицу обошли? Например, тут:
Мы последовательно идем по строкам и ищем "впадину". Дошли до первой единицы во второй строке.

Сообщение от Shamil1 3. Помечаем клетку как лужу и определяем её размеры: 3.1. Находим самую низкую граничащую клетку-кандидат

"Самая низкая клетка-кандидат" - это клетка-сосед "впадины", высота которой >= высоте самой "впадины", правильно я поняла?
Это двойка. Теперь

Сообщение от Shamil1 3.2. Если у кандидата есть более низкий "сухой" сосед, то больше нельзя увеличть лужу 3.3. Если у кандидата есть более низкий сосед, принадлежащий другой луже, то проверяем, можно ли объединить лужи

Но мы же только первую лужу нашли, откуда мы знаем, сухие соседи у кандидата или нет?

0

Сообщение от unspoken как мы поймем, что сосед "сухой" или "мокрый", если мы еще не всю матрицу обошли?

Если он у нас не помечен лужей, то сухой. Если на самом деле там лужа, мы найдём её позже, начиная с другой "впадины".

0

1. Помечаем все крайние клетки как "сухие" и находим среди них клетку (X) с минимальной высотой. Это будет текущая максимально возможная высота водяного столба (h)

2. "Расползаемся" от X обычным ДНФ (всю жизнь путаю это название). На каждом шаге имеем контейнер всех просмотренных. Для каждой добавляемой:

- если есть "сухой" сосед с высотой h2 < h, то среди всех просмотренных выбираем максимальный по высоте (и >= h2), помечаем его "сухим", и принимаем его высоту как новый h. Опять начинаем с той же клетки X (но уже с меньшим h). Это наверняка неоптимально, но надежно. Если же такого не нашлось, то h = h2 (просто понизили высоту столба без перезапуска)

- иначе если высота просматриваемой >= h, то она становится "сухой" и в контейнер просматриваемых не включается.

- иначе никаких выводов делать пока нельзя, включаем эту клетку в расползание

Если некуда больше ползти, все клетки контейнера = лужа с высотой h. Выбираем новую клетку X и возвращаемся к 2

Добавлено через 1 час 1 минуту
Наверное "перемудрил" - ведь если начинаем с "минимальной сухой", то не вижу как можем найти др "сухую" с меньшей высотой? Поэтому никакого "перезапуска" возникать не должно. Ну ладно

0

Задача решена в https://www.cyberforum.ru/cpp-beginners/thread1563805.html.
Просто и красиво)
Всем спасибо за помощь!

0

Сообщение от unspoken Задача решена в Задача на поиск луж в матрице. Просто и красиво)

Вообще-то это называется "brute force" - ну кому что нравится

0