|
Программист TH
292 / 147 / 12
Регистрация: 06.01.2009
Сообщений: 537
|
|
Задача про затопление острова.30.09.2009, 19:54. Показов 3683. Ответов 24
Метки нет (Все метки)
Прива всем.
------------------------------------------------------------------------- Вводится длина и ширина острова. Потом задаётся каждой клетке: земля это или вода. Прикол в том, что любой кусок земли, который хоть чем-то соприкасается (даже уголком) с клеткой воды - затопляется. Необходимо вывести площадь незатопленных участков. Т.е. 1 клетка - 10000 кв.м. ------------------------------------------------------------------------- Примечание: всё, что за полем - считать водой. Пример: ..... .***. .***. .***. ..... ------------------------------------------------- , где * - суша. На выходе: 10000. -------------------------------------------------- Принцип моего решения: 1. Вводим кол-во клеток на клеток. 2. Указываем суша или вода (массив 1 или 0) 3. Борьдюрчик, т.е. те клетки, которые как бы за картой заполняем водой, а для этого индексация с 1 начинается, а борьдюр отсюдога с 0-ля. 4. Проверяем 8 случаев соприкосновения вокруг каждой клетки в цикле на случай соприкосновения. 5. Отсюда счётчик капает, а в конце n*10000 и выводим. Работает! --------------------- Есть лучше схема решения?
0
|
|
| 30.09.2009, 19:54 | |
|
Ответы с готовыми решениями:
24
Задачка про острова Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника Острова в матрице (Единицы - это острова, а нули - море) |
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 30.09.2009, 20:14 | |
|
Ну например можно проверять только те клетки на которых находится суша.
Потому что если в клетке находится море, то водой второй раз оно заполнится уже не может
0
|
|
|
Программист TH
292 / 147 / 12
Регистрация: 06.01.2009
Сообщений: 537
|
||
| 30.09.2009, 21:29 [ТС] | ||
0
|
||
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 30.09.2009, 21:32 | |
|
Ты код покажи, а так чего воду в ступе толочь
![]() Я так вижу только два варианта. 1) От каждой клетки моря проверять затопит ли она соседнюю с ней сушу 2) Каждую клетку суши проверить - не затопит ли ее соседнее море
0
|
|
|
⚽
4191 / 1292 / 237
Регистрация: 27.07.2009
Сообщений: 3,962
|
|
| 30.09.2009, 21:39 | |
|
да просто пройти весь массив и проверять все суши - если вокруг нее нет воды, то считать ее не затопленной.
задача довольно легкая...
0
|
|
|
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
|
|
| 30.09.2009, 22:11 | |
|
Парочка оптимизаций во благо скорости, если действовать по твоему методу, а именно: вводить все в двухмерный массив:
С самого начала его запомнить нулями, а когда считываем островок - в массиве менять 0 на единицы, если это вода. И более существенное: Пробегаемся по массиву в целях найти сушу. Как только находим - проверяем с чем она граничит, если она хоть раз одним из углов касается воды - красим эту клетку клетку как затопленную, то есть присваиваем этому элементу значение скажем 2. Идем дальше, дальше проверяем либо чтобы вокруг клетки была хоть одна вода причем сама клетка - незатопленная суша - либо то что все окружающие ее 8 клеток либо суши, либо затопленные суши - тогда увеличиваем n. Добавлено через 1 минуту Код в студию!
0
|
|
|
⚽
4191 / 1292 / 237
Регистрация: 27.07.2009
Сообщений: 3,962
|
|||||||||||||||||||||
| 30.09.2009, 22:43 | |||||||||||||||||||||
|
на счет моего варианта:
пусть поле N на M. делаем массив:
0
|
|||||||||||||||||||||
|
125 / 123 / 0
Регистрация: 30.03.2009
Сообщений: 766
|
|
| 30.09.2009, 22:54 | |
|
еще вот какое дело - если остров один и без "дырок", то можно пробегаться только по береговой линии.
тогда скорость выполнения будет порядка O(N) а не O(N*N), как при просмотре каждой клетки))
0
|
|
|
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
|
|
| 30.09.2009, 22:56 | |
|
TAVulator, все-таки мой способ будет по-быстрее)
0
|
|
|
⚽
4191 / 1292 / 237
Регистрация: 27.07.2009
Сообщений: 3,962
|
||
| 30.09.2009, 23:02 | ||
|
фактически мой способ даже быстрее, т.к.: ты: пробегаем весь массив - помечаем затопленные - считаем не затопленные. я: пробегаем весь массив - считаем не затопленные.
0
|
||
|
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
|
|
| 30.09.2009, 23:26 | |
|
У меня быстрее - у тебя за каждую итерацию цикла поиска будет программа обращаться к 8 элементам массива - 8 раз залезать в память компа, у меня же будут такие случаи, когда будут проверены не 8 клеток)
Добавлено через 28 секунд Скорости будут одинаковые, если остров занимает весь прямоугольник) Добавлено через 4 минуты Кстати, если остров большой, то можно ипользовать метод Монте-Карло. =)
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 01.10.2009, 06:28 | |
|
В таких тестовых заданиях нет смысла измерять скорость.
Но если сильно хочется то измерять нужно по всем правилам.
0
|
|
|
Программист TH
292 / 147 / 12
Регистрация: 06.01.2009
Сообщений: 537
|
||||||
| 01.10.2009, 14:39 [ТС] | ||||||
0
|
||||||
|
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
|
||||||||
| 01.10.2009, 16:11 | ||||||||
|
Тут так
Если надо, могу написать.
0
|
||||||||
|
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
|
|
| 02.10.2009, 16:38 | |
|
Дэну походу уже пофиг на это.
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 02.10.2009, 16:54 | |
|
Ну он уже решил что работает
0
|
|
|
(Yellow_Duck)
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
|
|
| 02.10.2009, 17:46 | |
|
Да, вам не понять)
Надо решать чтобы работало максимально быстро и с минимальными затратами памяти.
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 02.10.2009, 19:31 | |
|
Это максимализм.
Нужно решать поставленную задачу в срок. Если скорость не устраивает - тогда и думать уже. Хотя конечно есть места где сразу требуется делать достаточно быстро. А максимализм проходит с возрастом ![]() Добавлено через 8 минут И кстати насчет оптимизации - когда-то давно я писал программы для МК-61. Вот там приходилось реально ужиматься ![]() Долго не мог избавиться от привычки делать все сверхоптимально.
0
|
|
|
Программист TH
292 / 147 / 12
Регистрация: 06.01.2009
Сообщений: 537
|
||
| 02.10.2009, 19:32 [ТС] | ||
Это в С++ надо думать.....
0
|
||
|
Тимуровец
445 / 285 / 50
Регистрация: 10.09.2009
Сообщений: 963
|
||
| 02.10.2009, 23:49 | ||
|
Что-то я не понял. Если тупо следовать условию задачи, то площадь незатопленных участков будет равна 0, т.к.
0
|
||
| 02.10.2009, 23:49 | |
|
Помогаю со студенческими работами здесь
20
Есть острова и мосты между ними. Нужно обойти все острова, побывав на каждом мосту по разу [Задача] Три острова Задача поиска минимального острова Интересная программа про "острова в море" Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
|
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога
SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
|
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога
Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip"
Извлеките архив и вы увидите. . .
|
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога
Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д.
Сборка примера
Скачайте. . .
|
|
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
|
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net
REST сервисы временно не работают, только через Web.
Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
|
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
|
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
|