![]() |
![]() |
@^WARlock^@ |
![]() ![]()
Сообщение
#1
|
![]() Пионер ![]() ![]() Группа: Пользователи Сообщений: 96 Пол: Мужской Реальное имя: John Репутация: ![]() ![]() ![]() |
Народ помогите написать программу.
Острова (определить кол-во островов на озере). Прога частично напоминает морской бой. Задается поле, на нем можно расставлять острова (один квадрат –ик один остров). После расставления островов, прога должна сосчитать их кол-во. |
![]() ![]() |
Lapp |
![]()
Сообщение
#2
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
1. Обнуляем счетчик островов N.
Ну, это понятно. 2. Проходим по всему массиву до встречи первой -1. Тоже понятно - идем до встречи с нехоженой землей. В самом начале в нашем массиве есть только 0 (вода) и -1 (земля). Затем земля перемаркировывается номером острова. Но -1 всегда означает землю, на которой мы еще не были (где не ступала нога человека ![]() 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. Вот так. Алгоритм небыстрый, но работает корректно, не собъется ни на какой самой запутанной комбинации. Ну что, сможешь составить блок-схему? ![]() -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
![]() ![]() |
![]() |
Текстовая версия | 14.07.2025 20:48 |