Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.78/18: Рейтинг темы: голосов - 18, средняя оценка - 4.78
Программист TH
 Аватар для DanUnited
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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
30.09.2009, 19:54
Ответы с готовыми решениями:

Задачка про острова
На старых школьных олимпиадах была такая задачка: Дана матрица (n*m), которая состоит из 1 и 0. Нули - это море, а единицы - острова....

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Острова в матрице (Единицы - это острова, а нули - море)
Имеется матрица (n*m) заполненная 1 и 0. Единицы - это острова, а нули - море. Если единицы находятся рядом по горизонтали или вертикали -...

24
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
30.09.2009, 20:14
Ну например можно проверять только те клетки на которых находится суша.
Потому что если в клетке находится море, то водой второй раз оно заполнится уже не может
0
Программист TH
 Аватар для DanUnited
292 / 147 / 12
Регистрация: 06.01.2009
Сообщений: 537
30.09.2009, 21:29  [ТС]
Ну например можно проверять только те клетки на которых находится суша.
Потому что если в клетке находится море, то водой второй раз оно заполнится уже не может
каким же образом? И насколько от этого усложнится задача....
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
30.09.2009, 21:32
Ты код покажи, а так чего воду в ступе толочь

Я так вижу только два варианта.
1) От каждой клетки моря проверять затопит ли она соседнюю с ней сушу

2) Каждую клетку суши проверить - не затопит ли ее соседнее море
0
Эксперт по компьютерным сетямЭксперт Pascal/Delphi
 Аватар для TAVulator
4191 / 1292 / 237
Регистрация: 27.07.2009
Сообщений: 3,962
30.09.2009, 21:39
да просто пройти весь массив и проверять все суши - если вокруг нее нет воды, то считать ее не затопленной.
задача довольно легкая...
0
(Yellow_Duck)
 Аватар для MadMag
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
30.09.2009, 22:11
Парочка оптимизаций во благо скорости, если действовать по твоему методу, а именно: вводить все в двухмерный массив:
С самого начала его запомнить нулями, а когда считываем островок - в массиве менять 0 на единицы, если это вода.
И более существенное: Пробегаемся по массиву в целях найти сушу. Как только находим - проверяем с чем она граничит, если она хоть раз одним из углов касается воды - красим эту клетку клетку как затопленную, то есть присваиваем этому элементу значение скажем 2. Идем дальше, дальше проверяем либо чтобы вокруг клетки была хоть одна вода причем сама клетка - незатопленная суша - либо то что все окружающие ее 8 клеток либо суши, либо затопленные суши - тогда увеличиваем n.

Добавлено через 1 минуту
Код в студию!
0
Эксперт по компьютерным сетямЭксперт Pascal/Delphi
 Аватар для TAVulator
4191 / 1292 / 237
Регистрация: 27.07.2009
Сообщений: 3,962
30.09.2009, 22:43
на счет моего варианта:
пусть поле N на M.

делаем массив:
Pascal
1
A: array[1..N+2, 1..M+2] of boolean;
заполняем его:
Pascal
1
2
3
4
5
6
For i:=1 to N+2 do
 For j:=1 to M+2 do
   A[i,j]:=0;
For i:=2 to M do
 For j:=2 to N do
  readln(A[i,j]);
ну и далее считаем:
Pascal
1
2
3
4
5
6
7
K:=0;
For i:=2 to M do
 For j:=2 to N do
  If (A[i-1,j-1])and(A[i-1,j])and(A[i-1,j+1])and
     (A[i,j-1])and(A[i,j+1])and(A[i+1,j-1])and
     (A[i+1,j])and(A[i+1,j+1])
  then inc(K);
в результате получаем ответ:
Pascal
1
writeln(K*10000);
0
125 / 123 / 0
Регистрация: 30.03.2009
Сообщений: 766
30.09.2009, 22:54
еще вот какое дело - если остров один и без "дырок", то можно пробегаться только по береговой линии.

тогда скорость выполнения будет порядка O(N) а не O(N*N), как при просмотре каждой клетки))
0
(Yellow_Duck)
 Аватар для MadMag
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
30.09.2009, 22:56
TAVulator, все-таки мой способ будет по-быстрее)
0
Эксперт по компьютерным сетямЭксперт Pascal/Delphi
 Аватар для TAVulator
4191 / 1292 / 237
Регистрация: 27.07.2009
Сообщений: 3,962
30.09.2009, 23:02
Цитата Сообщение от YeLLoW DucK Посмотреть сообщение
TAVulator, все-таки мой способ будет по-быстрее)
все, что ты описал - тот же метод, что и я привел, только ты зачем-то еще помечаешь затопленные острова, а я просто ищу оставшиеся острова.
фактически мой способ даже быстрее, т.к.:
ты: пробегаем весь массив - помечаем затопленные - считаем не затопленные.
я: пробегаем весь массив - считаем не затопленные.
0
(Yellow_Duck)
 Аватар для MadMag
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
30.09.2009, 23:26
У меня быстрее - у тебя за каждую итерацию цикла поиска будет программа обращаться к 8 элементам массива - 8 раз залезать в память компа, у меня же будут такие случаи, когда будут проверены не 8 клеток)

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

Добавлено через 4 минуты
Кстати, если остров большой, то можно ипользовать метод Монте-Карло. =)
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
01.10.2009, 06:28
В таких тестовых заданиях нет смысла измерять скорость.
Но если сильно хочется то измерять нужно по всем правилам.
0
Программист TH
 Аватар для DanUnited
292 / 147 / 12
Регистрация: 06.01.2009
Сообщений: 537
01.10.2009, 14:39  [ТС]
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
program pole;
uses crt;
var a,b,h,w,i,f:Integer;
earth:Array[0..000,0..31] of Integer;
begin
clrscr;
Writeln('Введите высоту поля:');Readln(h);
Writeln('Введите ширину поля:');Readln(w);
Writeln('Клетки заполняются с нижнего левого угла...');
Writeln('-- 0: море 1: суша --');
for a:=1 to h do
for b:=1 to w do
begin
Writeln ('Клетка: ',a,',',b); Readlb(i);
earth[a,b]:=i;
end;
{Теперь заполняем борьдюрчики..}
for i:=0 to h do
begin
earth[0,i]:=0;
earth[w+1,i]:=0;
earth[i,0]:=0;
earth[i,h+1]:=0;
end;f:=0;
{Тут я проверяю каждую клеточку...хе-хе}
for a:=1 to h do
for b:=1 to w do
begin
if((earth[a-1,b-1]<>0)and(earth[a,b-1]<>0)and(earth[a+1,b-1]<>0)and(earth[a+1,b]<>0)and
earth[a+1,b+1]<>0)and(earth[a,b+1]<>0)and(earth[a-1,b+1]<>0)and(earth[a-1,b]<>0))then
{все случаи жизни перечислил, впринципе если массив назывался бы просто "а", то было бы короче...}
f:=f+1;
end;
Writeln('Площадь,S = ',(f*10000));
readkey;
end.
Вот и всё, у меня работает....
0
(Yellow_Duck)
 Аватар для MadMag
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
01.10.2009, 16:11
Тут так
for a:=1 to h do
for b:=1 to w do
begin
Writeln ('Клетка: ',a,',',b); Readlb(i);
earth[a,b]:=i;
end;
Pascal
1
2
3
for a:=1 to h do
  for b:=1 to w do 
     Writeln ('Клетка: ',a,',',b); Readlb(earth[a,b]);

for a:=1 to h do
for b:=1 to w do
begin
if((earth[a-1,b-1]<>0)and(earth[a,b-1]<>0)and(earth[a+1,b-1]<>0)and(earth[a+1,b]<>0)and
earth[a+1,b+1]<>0)and(earth[a,b+1]<>0)and(earth[a-1,b+1]<>0)and(earth[a-1,b]<>0))then
{все случаи жизни перечислил, впринципе если массив назывался бы просто "а", то было бы короче...}
f:=f+1;
Здесь не надо писать begin и end, но суть та же - если ты хочешь сделать, чтобы программа быстрее работала, здесь надо делать так, как я писал. Иначе будет работать за O(64*N^2)а, так как N у тебя меньше 64, то будет скорость порядка O(N^3), чего в моем случае можно избежать.
Если надо, могу написать.
0
(Yellow_Duck)
 Аватар для MadMag
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
02.10.2009, 16:38
Дэну походу уже пофиг на это.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 16:54
Ну он уже решил что работает
0
(Yellow_Duck)
 Аватар для MadMag
1261 / 130 / 15
Регистрация: 16.10.2008
Сообщений: 733
02.10.2009, 17:46
Да, вам не понять)
Надо решать чтобы работало максимально быстро и с минимальными затратами памяти.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 19:31
Это максимализм.
Нужно решать поставленную задачу в срок.
Если скорость не устраивает - тогда и думать уже.

Хотя конечно есть места где сразу требуется делать достаточно быстро.

А максимализм проходит с возрастом

Добавлено через 8 минут
И кстати насчет оптимизации - когда-то давно я писал программы для МК-61.
Вот там приходилось реально ужиматься
Долго не мог избавиться от привычки делать все сверхоптимально.
0
Программист TH
 Аватар для DanUnited
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
02.10.2009, 23:49
Помогаю со студенческими работами здесь

Есть острова и мосты между ними. Нужно обойти все острова, побывав на каждом мосту по разу
Задача &quot;Острова и мосты&quot; (задача Эйлера). Есть острова и мосты между ними. Нужно обойти все острова, побывав на каждом мосту по разу. ...

[Задача] Три острова
Задача для 3-4 классов (судя по всему, олимпиадная). Я сам так и не решил. Помогли решить математики. Решается элементарно. Ответы и...

Задача поиска минимального острова
Не могу решить задачу.... ответ должен быть 68, а у меня выходит 91, подскажите пожалуйста как и что нужно исправить! Сломал голову...

Интересная программа про "острова в море"
вот суть задачи http://www.nelidovo.edu.ru/olimpiads/informatica/Allolimpiads/meshdunarod/meshdunarod1992.html задача старая, но прошу...

Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы.
читаю книгу Эрика Фримена про основы javascript.В конце 5 главы есть задачка про взлом кода.Никак не могу понять как ее решить.НЕ понимаю...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
влияние грибов на сукцессию
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 ). Также. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru