pajerovaliero (pajerovaliero) wrote in ru_programming,
pajerovaliero
pajerovaliero
ru_programming

На собеседовании дали задачку, я её решил, отправил, программеры посмотрели и отказали.
Поэтому думаю, что можно публиковать всё, кроме явок и паролей.
Задачка была такая: дана матрица высот
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, только начать с того же самого элемента.

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

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

Короче, смысл в том, что ищутся впадины и заливаются. Потом уровень воды в этой впадине проверяется на то, может ли он являться дном другой впадины (есть края сдерживающие воду?) и т.п. Когда новый построенный уровень воды озера окажется неспособным нести поверх себя воду, идём строить другое озеро. Если все озера ограничены каким-то высоким далёким забором, то в момент строительства последнего озера оно обнаружит, что сливается дном с кучей других и рассмотрит их поверхности как своё дно и построится от этого дна выше. Короче, надо делать видео визуализацию, шарить бы в blender-е ))

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

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

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

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

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

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

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

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

UPD: (http://pajerovaliero.livejournal.com/803.html)
UPD: chest_i_razym взял и придумал гораздо проще: http://community.livejournal.com/ru_programming/1126799.html?thread=17245327#t17245327
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 63 comments