Острова Опции

[@^WARlock^@]

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


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

Прога частично напоминает морской бой. Задается поле, на нем можно расставлять острова (один квадрат –ик один остров). После расставления островов, прога должна сосчитать их кол-во.

[Lapp]

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.

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

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