|
|
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
В море находится шестиугольный остров, сотворенный из вертикальных 6-угольных плит, плотно подогнанных друг к другу. Площадь горизонтального сечения каждой плиты равна 1, а высота верхней грани над уровнем моря - некоторое целое число больше 0, отдельно указывается для каждой плиты (на рисунке обозначено цифрами). Есть массив со всеми высотами. Во время прилива остров полностью уходит под воду. Найти суммарный объем воды, который останется в лужах на острове, после отлива. На рисунке оный объем равен 3, вода останется в центральной ячейке и ячейке сверху-справа от неё. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 11:51 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Ограничения на сложность или что-то типа есть? Можно просто решение в лоб: 0) Обозначем "плиты море" = 0 1) Для каждой плиты находим все возможные пути к морю (с условием a[n] > a[n+1]). Для каждой плиты сохраняем массив плит, которые участвовали в путях к морю 2) Находим локальные минумы 3) Для каждого локального минимум рекурсивно обходим его соседей с проверкой, находятся ли они в "чьем-то пути" из первого пункта. Если нет, то добавляем его в лужу. 4) В итоге в лужах находятся группы плит. У каждой лужы находим минимального соседа 5) Объем = Сумма всех групп по (минимальный сосед - высота плиты) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 12:20 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
SpringMan Ограничения на сложность или что-то типа есть? ну а так - чем меньше, тем лучше) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 12:24 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Переусложним в первом решении, можно чуть проще: 0) Обозначем "плиты море" = 0 1) Для каждой плиты находим все возможные пути к морю (с условием a[n] > a[n+1]). Для каждой плиты сохраняем флаг "есть или нет выход к морю" 2) Находим локальные минумы 3) Для каждого локального минимум рекурсивно обходим его соседей с проверкой есть ли у него выход к морю. Если выхода к морю тоже нет, то добавляем эту плиту в лужу 4) В итоге в лужах находятся группы плит. У каждой лужы находим минимального соседа 5) Объем = Сумма всех групп по (минимальный сосед - высота плиты) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 12:32 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Нудно описывать исходные данные. Обычно сотовый порядок узлов хорошо намапливается на матрицу где мы (условно) считаем каждую ячейку 6 связной. Типа Код: sql 1. 2. 3. 4. 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 12:54 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Если для настоящей картинки (нужна матрица по трем линиям?): рассуждения идут из центра если по шести направлениям высоты выше, то "хорошо". если по одному из направлений высота меньше, переходим на это направление. и снова перебираем пять (или три) направлений. как-то так ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 13:11 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Просто прогаммировать структуры данных с графами - нудотство. Обычно мы пытаемся применять сначала коллекции. Потом hashmaps, потом деревья. Графы идут в самом конце по степени популярности использования. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 15:18 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
mayton Просто прогаммировать структуры данных с графами - нудотство. +1 Предлагаю шестигранник сделать квадратным ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 15:27 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Dima T mayton Просто прогаммировать структуры данных с графами - нудотство. +1 Предлагаю шестигранник сделать квадратным ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 15:55 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 можно и так, только уточнить, что касание углами плотное и воду не пропускает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 16:12 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Basil A. Sidorov Имя пользователя1 можно и так, только уточнить, что касание углами плотное и воду не пропускает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 16:32 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 в шестиугольнике касание сторонами ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 16:49 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Dima T mayton Просто прогаммировать структуры данных с графами - нудотство. +1 Предлагаю шестигранник сделать квадратным +1 В комьютерных играх типа Panzer General игровая поверхность так и задана. Более того там хитрость есть как на квадрате больше ячеек впихнуть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:26 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Перебираем для каждого островка соседей. Если все 6 выше - тут лужа. Все. Всем спасибо все свободны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:31 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Хотя погорячился да.. Все не так.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:33 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Basil A. Sidorov, касание любой пары шестиугольников никому не мешает. а у квадратов, в реальном мире, не может так быть, чтобы А касался D, и в то же время B касался С (см. картинку). Потому отдельное пояснение про углы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:35 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Это копи-паста с одной из олимпиадных задач. Только там дождь капал на квадратные столбы и надо было посчитать высоту луж после дождя. Границы столбов по краям уходили в минус бесконечность тоесть по краям вода стекала вниз. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:37 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
АСУ ТПшник Хотя погорячился да.. Все не так.. Это в любом случае рекурсия. Изюминка будет в условии выхода. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:40 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Мне кажется надо пытаться представить все с точки зрения воды - где она упрется не в море , стекая. А когда эти самые области уже конечное число - вот тут применять сравнение высот и прочее и прочее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:46 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
1. Крайние hexxagons которые упираются в море - надо приравнять к некому минимальному числу типа MIN_INTEGER. 2. Далее должен быть некий цикл по всем оставшимся hexxagons, где мы просто делаем min(x,y) по уровню воды между всеми соседями. 3. Завершаем алгорим когда уровни воды перестали понижаться. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 17:52 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Или я не понял, или 51325 лужу с двумя минимумами вы пропустите. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 18:30 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Так же крайние клетки могут быть разной высоты. Не все так просто. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 18:31 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Что-то типа по капле упало на каждый хекс. И множится она деревом на все клетки, которые ниже текущей. Уплыла в море - вычеркиваем, нет - ищем минимумы. Нашли все минимумы. В каждом минимуме - поднимаем уровень на один. - соответсвенно на все граничные хексы пуляем очередную каплю. И так далее и тому подобное. Куча граничных условий, а если еще и на язык переклывать, не кислая такая программа выйдет. Изящного решения мне не видно пока. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 18:38 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Хм.. может инвертировать поле - самая высокая клетка становится самой низкой, тогда все локальный максимумы - потенциальные точки для дна лужи. А вот как ее края посчитать, вот это задачка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 18:40 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, Можно пойти от противного, закрашивая ячейки сливающиеся в океан цветом "Океан". В лоб: верхний ряд 1,4,3 - "Океан" второй ряд 1, 5, , 5 - "Океан", 1 - нет выхода в океан "Лужа" (все окружающие выше или "Лужа") третий ряд 2, 3, 6 - "Океан", 2 - нет выхода в океан "Лужа" (все окружающие выше или "Лужа"), 4 - неизвестно четвертый ряд 2, 6, 2 - "Океан", 4 - неизвестно пятый ряд 3, 1, 2 - "Океан" обрабатываем оставшиеся, остались две 4-ки, обе получаются "Океан". Можно идти по спирали сначала внутрь, потом наружу, по идее должны закрыть даже сложные случаи, но не уверен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2020, 18:43 |
|
||
|
|
start [/forum/topic.php?fid=16&tid=1339799]: |
0ms |
get settings: |
10ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
169ms |
get topic data: |
12ms |
get forum data: |
2ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
| others: | 249ms |
| total: | 523ms |
| 0 / 0 |
