На собеседовании дали задачку, я её решил, отправил, программеры посмотрели и отказали.
Поэтому думаю, что можно публиковать всё, кроме явок и паролей.
Задачка была такая: дана матрица высот
9,9,9,9,9,9,9
9,1,1,5,1,1,3
9,9,9,9,9,9,9
каждый член матрицы выражает высоту земли в этой точке. Т.е получается такой рельеф. За краями матрицы - минус бесконечность. Ноль в качестве значения одного из членов матрицы - тоже минус бесконечность, дырка т.е.

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

0,0,0,0,0,0,0
0,5,5,0,3,3,0
0,0,0,0,0,0,0

Есть ли готовый алгоритм для этого?
Мной придуманный заключается вот в чём:
1. Организуем "структуру данных", в которой каждый элемент может понимать, кто его соседи, касается ли он дырок, краёв. Т.е. чтобы можно было взять любого и определить, кто у него сверху, снизу, справа, слева и т.п.
2. Одновременно с этим есть список, содержащий указатели на все эти элементы. Используется для обхода.
3. Берём первый элемент из списка, запускаем с него попытку "поиска дна". Его высота = N - это максимум уровня земли в этой точке, либо уровня воды в ней (если она была туда залита ранее).
Логика в том, чтобы найти множество элементов, каждый из которых либо:
- высота=N, связан отношением соседства с другими равным себе по высоте.
- высота=N либо связан отношением соседства с элементом, выше его.
4. Если такое множество найдено, то выглядеть оно будет как плоский кусок поверхности, со всех сторон ограниченный элементами выше него, т.е. это будет место, куда можно залить воды. Основной вопрос - сколько.
5. Присвоить всем элементам из этого множества уровень воды равный минимальному ограничивающему это "дно" элементу. Т.е. так мы зальём это дно водой до уровня, откуда ей некуда убежать.
6. Переход на 3, только начать с того же самого элемента.

Смысл в том, что мы нащупываем любое дно, хоть мелкую впадинку и дальше пытаемся из неё вырасти. На каждой новой итерации мы будем иметь дело с новым уровнем дна, который будет неубывающий, если мы имеем дело с глубоким озером, которое "по ступенькам" поднимается. Будет новая итерация с разведкой границ нового дна на каждой ступеньке.

Если в очередной раз целое множество составить не удалось, значит встречена дырка, край рельефа, либо элемент ниже дна, который не позволит налить воды больше - она утечёт вниз.

Да, в рельефе может иметься множество локальных озёр, которые все ограничены чем то выше них, ну типа:

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

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

Недостаток - повторные прохождения по нескольку раз одной и той же клетки в ходе подьёма уровня воды по ступенькам, порой даже повторный проход целых озёр.

Т.е. такая вот штука инкрементирующая, динамический алгоритм наверное это называется.

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

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

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

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

http://pajerovaliero.livejournal.com/803.html

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

RT183nu88блин, всё, вопрос закрыт, надо было с краёв херачить, было бы в сто раз быстрее... чёрт ) алгоритм с "крайний наименьший" )
ты главного не сказал: те пиплы (которые "тестировали" тебя) были правы или нет?
уже пофиг, отказ получен, больше ничё меня не интересует )
Сейчас я вижу, в чём ещё могла быть лажа - не увидел такого решения, когда можно с краёв начинать "в обнимку" В ОДИН ПРОХОД заполнить все хитрые впадины и мультиозёра. Всё, это была самая приличная вакансия в городе, теперь тока застрелицо )

Да я понимаю, что простая, решение сразу в голову пришло, потом второе более экономичное, а оказывается есть третье, просто идеально клёвое )

RT183малейшая "полезная" вещь под строжайшим запретом
Да собственно и у нас это начинают понимать. Наш местный супер-хирург пишет:
пипец, на любой конференции язык на замок, потому что пиздят в наглую идеи,
и через неделю уже делают ТАМ (на Западе)
(-;

RT183nu88RT183малейшая "полезная" вещь под строжайшим запретом
Да собственно и у нас это начинают понимать. Наш местный супер-хирург пишет:
пипец, на любой конференции язык на замок, потому что пиздят в наглую идеи,
и через неделю уже делают ТАМ (на Западе)
(-;
так и есть
ты не знаешь насколько там контроль со стороны ну простых преподов например
Они (детишки, студики) у них консультируются по любому поводу; там вот так просто не письнешь
Со стороны конечно выглядит как будто "свободная страна"
Никуя; там пистец
А что это за сайт такой -- http://www.spoj.pl/ ?

Пытаюсь понять, в чём смысл сайтов.
Ты находишь там постановку проблемы, выполняешь решение и публикуешь там? Кроме проверки себя, в чём ещё может быть смысл?

Очень интересно, не знал. Математика всю жизнь интересовала, но к этим кругам не пренадлежал никогда ) Алгоритмы придумываю на базе высшего радиотехнического образования, никакой прикладной математики, а эти люди ведь наверное все с физ.мат.-лицеев и универов, монстры, жжесть )
Ладно, пойду александреску читать )

Тот алгоритм, который в один проход всё делает, о котором я тут зарекался, он и с дырками обходится клёво. Надо будет реализовать и выложить. Блин, какие вы сайты клёвые знаете.