Хай всем,

нет, парни, вы - злодеи!!! Заглянул в тему, прочитал суть задачи, дальше специально смотреть не стал, и не успокоился, пока сам не решил. Написал на шарпе, консольная прога и исходник - внутри архива.

ОГРОМНАЯ просьба потестить на самых причудливых данных и найти ошибки. Защита от дурака не делалась, это звиняйте...

Запуск: puddles.exe FileName.txt
FileNme.txt должен содержать в первой строке количество строк и колонок (не перепутайте), дальше идёт матрица с данными любой размерности, не менее чем 3х3. Значения уровней - от 1 до 9, с любым количеством "сливов" по краям. "Сливы" могут идти подряд.
Например, для файла с данными:

14 17
9 9 9 5 6 5 9 9 5 9 9 9 9 9 7 9 9
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5
9 4 4 4 4 0 4 4 4 4 4 4 4 4 4 4 7
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 7
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 7
5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9
6 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5
9 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9
9 9 9 5 5 9 6 9 9 9 9 5 9 9 9 9 9

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

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 2 2 0 0 0 0 0 0 0 0 0 0 1 0 0
0 2 4 2 0 0 0 0 1 1 1 1 1 0 2 3 0
0 2 2 2 0 0 0 0 1 1 1 1 1 0 0 0 0
0 0 0 4 4 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 4 4 0 0 0 0 0 0 0 0 0 0 4 0
0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0 1 4 3 2 1 0 0 0
0 0 0 0 1 1 1 1 0 2 0 0 0 4 0 0 0
0 0 0 0 0 0 1 1 0 3 0 2 0 3 0 0 0
0 0 0 0 0 0 1 0 0 4 0 0 0 2 0 0 0
0 1 2 3 0 0 0 0 0 1 2 3 4 1 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 2 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Вроде, так и должно быть.
Можно проверить на исходных данных в начальном посте.

rmullVadimPanov
Заглянул в тему, прочитал суть задачи, дальше специально смотреть не стал, ...

Зря. Если б посмотрели, то увидели бы, что решение можно проверить на этой задаче.
Это несколько разные задачи. Я говорил про ту, что озвучена в первом посте данной темы, при чём тут ссылка?

rmull
В вашем примере уровень воды в каждой клетке области с высотой = 4 должен быть одинаков, и равен нулю, потому что вода в дырку стекает. А у вас фигня какая-то в ответе.
Сорри, конечно, я ступил и залил для примера не те данные!
Вот верные исходные данные:

14 17
9 9 9 5 6 3 9 9 5 9 9 9 9 9 7 9 9
9 3 3 3 9 9 9 9 9 9 9 9 9 9 6 9 9
9 3 1 3 9 9 9 9 6 6 6 6 6 9 5 4 9
9 3 3 3 9 9 9 9 6 6 6 6 6 9 9 9 9
9 9 9 1 1 9 9 9 9 9 9 6 6 7 7 6 9
9 9 9 1 1 9 9 9 9 9 9 9 9 9 8 1 5
9 9 9 9 2 9 9 9 9 9 9 9 9 9 9 9 7
9 9 9 9 2 9 9 9 9 4 1 2 3 4 9 9 7
9 9 9 9 4 4 4 4 9 3 9 9 9 1 9 9 7
1 2 3 4 9 9 4 4 9 2 9 7 9 2 9 9 9
9 9 9 9 9 9 4 6 9 1 9 9 9 3 9 9 9
4 3 2 1 9 9 9 8 9 4 3 2 1 4 9 7 5
9 9 9 9 3 3 3 7 9 9 9 4 9 9 9 5 9
9 9 9 1 4 9 6 9 9 9 9 5 9 9 9 9 9

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

rmull
Задача по ссылке - это вариант задачи, описанной в этой теме, но без сливов внутри матрицы. Так что алгоритм можно легко на ней проверить.
Уважаемый, задача по ссылке просит найти максимальный объём воды, который получится в образовавшихся озёрах.
Тогда как у тредстартера задача звучит так:
"Необходимо выдать результат о том, где какие озёра образуются после длительного дождя или после опускания этой конструкции в море и подёма из него. Вода может переливаться с каждой клетки только в 4 направлениях.
Результат пусть будет, скажем, в абсолютной высоте уровня воды в данной точке."
Разница есть?

rmullVadimPanov
Разница есть?

В задаче по ссылке нужно выдать максимальный суммарный объём воды. Это значение равно сумме элементов матрицы, которую находит ваша программа. Я думаю, вам не должно составить труда найти эту сумму :)
Гм... Не собирался решать "задачу по ссылке"... Не искушайте меня :-)

У меня в реализации вся поверхность тупо заливается водой, затем обходом по краям ищутся "сливы", через которые вода может уйти и далее шагаем внутрь матрицы, уравнивая уровни (каламбур!) между соседними ячейками там, где это возможно. Т.е. внутренние лужи, не имеющие сливов по краям вообще не трогаются. А чтобы найти максимальный объём нужно найти все лужи, какие есть, и высчитать их объём. Я даже знаю - как... Блин... rmull, ты - злодей, я щас опять на этом залипну и пока не решу - не успокоюсь!

"Мой английский хромает, он хороший, но он хромает..."(с)
В задаче просится найти:
computes maximal water volume, which may gather in puddles after the rain

я правильно понимаю, что надо найти суммарный объём воды во всех лужах, или надо найти лужу с максимальным объёмом?

rmull,

Создал аккаунт, отослал код для решения этой задачи :-), получил "time limit exceeded"... :-(

Интересно, как оно у них считается? У меня же на компе быстро отрабатывает...

VadimPanovrmull,
Интересно, как оно у них считается?
И как они учитывают разную скорость для разных языков? Одно дело С++, другое - тот же C#...

rmullVadimPanovrmull,
Какая у вашего решения сложность? У меня решение со сложностью O(n*m*log(n*m)) на C++ выполняется за 0.11 секунд.

А хз... Как посчитать?
VadimPanov
И как они учитывают разную скорость для разных языков? Одно дело С++, другое - тот же C#...

Никак. 7 секунд - общий time limit для всех языков. Но в случае с C# это не должно быть проблемой, потому что он практически не уступает по скорости C++.
Интерпретатор не уступает по скорости скомпилированному в машинные команды коду? Гм...

RT183.1,

Извини, ничего не понял из твоего поста. Можешь сказать другими словами?