IPB
ЛогинПароль:

> Острова
@^WARlock^@
сообщение 28.02.2007 12:06
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 96
Пол: Мужской
Реальное имя: John

Репутация: -  0  +


Народ помогите написать программу.


Острова (определить кол-во островов на озере).

Прога частично напоминает морской бой. Задается поле, на нем можно расставлять острова (один квадрат –ик один остров). После расставления островов, прога должна сосчитать их кол-во.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
Lapp
сообщение 2.05.2007 8:02
Сообщение #2


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


1. Обнуляем счетчик островов N.
Ну, это понятно.

2. Проходим по всему массиву до встречи первой -1.
Тоже понятно - идем до встречи с нехоженой землей. В самом начале в нашем массиве есть только 0 (вода) и -1 (земля). Затем земля перемаркировывается номером острова. Но -1 всегда означает землю, на которой мы еще не были (где не ступала нога человека smile.gif).

3. Если ни одной -1 не было найдено - выходим.
И это понятно - неизведанные земли кончились. Выход из процедуры.

4. Увеличиваем N на 1.
Если нашли -1 - значит, нашли новый остров. Увеличиваем счетчик островов.

5. Меняем значение найденной клетки на N.
Столбим землю. Вместо -1 записываем номер острова

6. Сбрасываем флаг.
Флаг будет установлен, если мы найдем новые клетки этого же острова (то есть -1 соседние к N). Он нужен нам, чтобы понять, когда закончится процесс перемаркировки текущего (N-го) острова.

7. Проходим циклом по всему массиву. Если текущий элемент равен -1, а один из его четырех соседей равен N, то меняем его на N и устанавливаем флаг.
Цикл по всему массиву - это двойной цикл по координатам, как обычно (по строчкам, сверху вниз). Перемаркировка текущего острова производится не за один цикл. Это я поясню потом на примере

8. Если флаг установлен - переходим к п.6
Установленный флаг означает, что соседние клетки были найдены. А это значит, что могут быть и соседние к новым найденным. Значит, надо пройти еще раз..

9. Если флаг сброшен - переходим к п.2
Сброшенный флаг значит, что за последний проход не было найдено новых соседних клеток к текущему острову. Значит, мы нашли все. Можно переходить к поиску нового острова.

Вот пример.
Представь себе остров, закрученный наподобие спирали (# означает -1, а ~ - воду, то есть 0 ):
Код
~~~~~~~~~~~~
~##########~
~#~~~~~~~~#~
~#~######~#~
~#~#~~~~#~#~
~#~#~~#~#~#~
~#~####~#~#~
~#~~~~~~#~#~
~########~#~
~~~~~~~~~~~~

Когда мы его только нашли, ситуация такая:

~~~~~~~~~~~~
~1#########~
~#~~~~~~~~#~
~#~######~#~
~#~#~~~~#~#~
~#~#~~#~#~#~
~#~####~#~#~
~#~~~~~~#~#~
~########~#~
~~~~~~~~~~~~

После первого прохода мы получим:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~#~1~
~1~~~~~~#~1~
~11111111~1~
~~~~~~~~~~~~

Перемаркированы только те клетки, которые правее-ниже от пройденных.

После 2-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~#~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

После 3-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

Медленно продвигаемся наверх, по клетке за проход по всей матрице..
....
После 9-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~##1111~1~
~1~#~~~~1~1~
~1~#~~#~1~1~
~1~####~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

.....


После 11-го остается только одна клетка:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~111111~1~
~1~1~~~~1~1~
~1~1~~#~1~1~
~1~1111~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

После 12-го все клетки закрашены, но флаг все же установлен.
На 13-м проходе флаг установлен не будет: больше нет -1, соседних к 1.

Вот так. Алгоритм небыстрый, но работает корректно, не собъется ни на какой самой запутанной комбинации.

Ну что, сможешь составить блок-схему? smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
@^WARlock^@   Острова   28.02.2007 12:06
Lapp   Не совсем понятно, в чем проблема. Если одна клет...   28.02.2007 13:43
T i m e   Мне тоже не понятно... @^WARlock^@ поконкретней ...   28.02.2007 18:42
@^WARlock^@   Проблема в том. 1) Допустим я сделал поле, как п...   1.03.2007 10:31
Lapp   Проблема в том. 1) Допустим я сделал поле, как ...   1.03.2007 11:32
T i m e   Используй чтение клавиши с помощью: key := readke...   1.03.2007 17:59
TarasBer   Используй чтение клавиши с помощью: key := readke...   1.03.2007 20:16
T i m e   Я отвечал не на исходный вопрос, а на тот который...   1.03.2007 20:44
Lapp   TarasBer, а чем тебе так не понравился ReadKey? Че...   2.03.2007 5:50
TarasBer   TarasBer, а чем тебе так не понравился ReadKey? Ч...   3.03.2007 19:07
@^WARlock^@   Взял морской бой и убрал лишнее. Вот, что я име...   3.03.2007 7:26
volvo   2 Time: ты наказан? Вот и сиди в карцере! Еще ...   3.03.2007 15:24
@^WARlock^@   Вижу вы тут спор затеяли. Но всетаки:   4.03.2007 12:45
Lapp   Вижу вы тут спор затеяли.@^WARlock^@, спор, как ты...   6.03.2007 4:55
@^WARlock^@   Да просто подсчитать острова, их кол-во должно о...   6.03.2007 9:23
@^WARlock^@   Эот код действителен если остров состоит из одной ...   25.03.2007 12:40
Lapp   если мой остров состоит не из одной клетки, а бол...   25.03.2007 12:43
@^WARlock^@   Я его уже смотрел, но не смог реализовать.   25.03.2007 12:45
Lapp   Мне неясно - в чем именно трудность? Я сейчас тупо...   25.03.2007 13:46
@^WARlock^@   Проссмотрел выше указанный код, начиная с {реализа...   28.03.2007 4:30
Lapp   Из-за чего так получается? Насколько я смог по...   28.03.2007 6:13
@^WARlock^@   С подсчетом островов я разобрался. Как теперь с...   5.04.2007 11:29
@^WARlock^@   Так, как можно заполнять массив в графическом режи...   7.04.2007 13:03
Lapp   Молодец, прога, вроде, работает! :) как можно...   8.04.2007 5:25
@^WARlock^@   На какие и как? Просто располовинить? :blink: В...   9.04.2007 10:06
Lapp   На какие и как? Просто располовинить? ... Труба...   9.04.2007 12:38
@^WARlock^@   Вот понавтыкал пробелов, может лучше будет. А во...   12.04.2007 5:21
Lapp   как в графмческом режиме вывести числовую перемен...   12.04.2007 5:36
@^WARlock^@   В моей последней проге идет хоть какое-то заполнен...   13.04.2007 7:30
@^WARlock^@   Как и "все", я решил забить на подключен...   18.04.2007 13:17
@^WARlock^@   Народ, подскажите алгоритм выполнения подсчета ост...   22.04.2007 6:09
Lapp   Народ, подскажите алгоритм выполнения подсчета ос...   22.04.2007 11:47
@^WARlock^@   Точно, а я и не замечал(наверное потомучто больше...   22.04.2007 12:58
Lapp   Не подскажите, из-за чего так происходит? И, что ...   23.04.2007 10:35
Lapp   И, что надо изменить в процедуре SCHET, чтобы про...   24.04.2007 6:18
@^WARlock^@   Советы, по поводу того, что процдура SCHET не ко...   24.04.2007 5:39
Lapp   На какие вопросы я не отвечаю? Вот на этот: @^W...   24.04.2007 5:57
@^WARlock^@   Не понимаю почему я тупил столько времени. LAPP -...   27.04.2007 11:02
Lapp   Не понимаю почему я тупил столько времени. Бывает...   27.04.2007 11:43
@^WARlock^@   LAPP - говорил, что поможешь реализовать блок-схем...   2.05.2007 4:23
Lapp   LAPP - говорил, что поможешь реализовать блок-схе...   2.05.2007 5:01
@^WARlock^@   Последний рабочий вариант программы: Подскажи, п...   2.05.2007 6:39
Lapp   Подскажи, по какому принципу работает твоя прога(...   2.05.2007 6:42
Lapp   1. Обнуляем счетчик островов N. Ну, это понятно. ...   2.05.2007 8:02
@^WARlock^@   У меня вот, что получилось:   2.05.2007 10:00
Lapp   У меня вот, что получилось: Пока что сыровато, я...   2.05.2007 10:32
@^WARlock^@   Я в блок-схемах не силен. Может тогда предложишь ...   2.05.2007 11:40
Lapp   Я в блок-схемах не силен. Может тогда предложишь ...   3.05.2007 8:45
@^WARlock^@   Как я понял, это выход в твоей проге, а в моей эт...   3.05.2007 5:08
@^WARlock^@   Решил перед сдачей проги окончательно её протестир...   10.05.2007 7:08


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 14.07.2025 20:48
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"