Алгоритм для игры

[LSL]

Дан двумерный массив, заполнен 1 и 0.
Некоторая область нулей "окружена" единицами.
Областей может быть несколько и они могут граничить друг с другом.

Нужно подсчитать "окружённые" нули.

Пример: (16*8)

0000001100000000
0101110010011100
0010000001100100
0100010000111000
0010000100000100
0010001011000100
0011110001000100
1110000001111100

В этом примере есть две "замкнутые" единицами области
граничащие друг с другом. В одной 33 нуля, в другой 2.

Как их подсчитать программно.

Алгоритм нужен для игры.

[vicmb]

А по диагонали могут окружать?

[Spectator]

Что значит граничить
Либо они окружены единицами либо нет
А вообще можно так: ищем (перебором) ноль
далее рекурсивно налево, направо, вверх, вниз смотрим что там. Есть два варианта - либо область нулей ограничена 1 либо она касается границы. Т.о. рекурсивная функция:
1) Возвращает 1 если встретила на пути единицу
2) Возвращает 0 если встретила на пути границу массива
3) Если на вызванном месте 0, то возвращает 0 если возвратила 0 одна из вызванных соседних клеток, иначе - 1
Ну и чтобы не зациклица проверенные места надо вычеркивать. Ну и нули считать по ходу дела.
Надеюсь понятно

[LSL]

vicmb
Да. В примере видно...

Spectator

Что значит граничить
Либо они окружены единицами либо нет

Я имел в виду что окружённых областей может быть несколько.
Они могут граничить ,перекрывать друг друга.
Или быть одна в другой !
Так вот надо посчитать окружённые нули во всех областях.

Пример. (4 области)

00000000000000000000000000000000
00111111111111111111111111111100
00100000000000000000000000000100
00100000000000000000000000000100
00100000000000000000000000000100
00100001111110000000000000000100
00100001010010000000001111111100
00100001001010000000001000000000
00100001111110000000001000000000
00100000000000000000010100000000
00100000000000000000100010000000
00100111100000000001001001000000
00101000010000000000100010000000
00100100100000000000010100000000
00111100111111111111111000000000
00000000000000000000000000000000

Надеюсь понятно
Попробую понять.

[zerg]

такое же задание(почти) на олимпиаде по информатике (10 класс) было - я решил тогда, правда как не помню.(помню брал любую единицу и двигался по соседним единицам в какую то сторону до тех пор пока не возвращался на исходное "1"-это и есть замкнутый круг) больше ничего не помню. кстати я тогда решил её(только её) и получил 3 место(там она чють попроще была).
-----------------------------
Может натолкнул на мысль?
Если нет - извиняйте.

[Spectator]

zerg
Тоже вариант
При этом надо отмечать пройденные 1 по ходу и если круг замкнулся то сканированием (слева направо сверху вниз) посчитать количество 0 внутри
только от рекурсии все равно не уйдешь. Так как внутри каждого круга может быть еще один круг - тогда это будет две разных области и рекурсия вообще будет сложнее (надо передавать внутрь маску в которой надо искать 1 и круг образованный этими единицами).
Т.о. отталкиваться можно и от единиц (как у zerg) и от нулей (как у меня). Мой алгоритм чуть сложнее понять, но реализация представляется мне проще. Если реализовывать по моему хватит одной булевой матрицы (глобальной), а у zerg - несколько (передающихся в рекурсию).
Может я и не прав, я не оправдываю свой вариант, а токмо хочу помочь LSL.

[LSL]

zerg Spectator
это и есть замкнутый круг
Ну и что ? А как теперь в нём нули посчитать...

если круг замкнулся
Беда в том что "круг" может граничить с другими..
То есть как его обойти, если стенки расходиться будут ?
Как на примере...

сканированием (слева направо сверху вниз)
А если "круг" неправильный ? Внутрь вогнутый...
Как на примере...

Наверно я чего-то не понимаю...

А давайте-ка исходники в форум!
И сразу понятно будет...

Кто у нас лучший кодер ?

[Bais]

Сделай волновым алгоритмом - ищеш выход, если нет то все ок.
Волновой алгоритм состоит в пуске волны распространяющейся во все стороны (помечается область, где мы уже были). Ищется кратчайший путь, но тебе достачно выяснить, что его нет

[Spectator]

Bias
А я что написал? Просто сами мы неграмотные, в университетах не учились Про то, что это волновой алгоритм не знаем (иш ты як москали перебор с рекурсией называют
LSL:
>>это и есть замкнутый круг
>Ну и что ? А как теперь в нём нули посчитать...
Я сказал сверху вниз, слева направо if 0 then cnt++

>>если круг замкнулся
>Беда в том что "круг" может граничить с другими..
>То есть как его обойти, если стенки расходиться будут ?
>Как на примере...
Дык я же говорю - на примере у нас есть круг и в нем еще круг - то что стенки совпадают - не беда, все равно он вложенный. Представь попу - т. е. круг разделенный линией. Мы нашли внешний круг вместе с разделающей линией. Потом внутре ищем более меньший круг, не совпадающий по всем точкам со внешним. Я уже сказал что рекурсия будет непростой.

>>сканированием (слева направо сверху вниз)
>А если "круг" неправильный ? Внутрь вогнутый...
>Как на примере...
Ну и что. Есть такая задача - лежит ли точка внутри фигуры? Ответ - надо пустить луч из бесконечности в эту точку по любой прямой (на практике пускают луч по прямой паралельной оси X или Y из точки за пределами фигуры). Если этот луч пересекает стенки фигуры четное число раз - значит точка за пределами фигуры. Иначе - внутре. Причем фигура может быть и впуклой. Главное, чтобы замкнутая. Намек понял?

>А давайте-ка исходники в форум!
Облезешь, неровно обрастешь Некрасивым станешь

>И сразу понятно будет...
>Кто у нас лучший кодер ?
Конечно же ты

[RomanPshenichny]

> Некоторая область нулей "окружена" единицами.
> Областей может быть несколько и они могут граничить
> друг с другом.
> Нужно подсчитать "окружённые" нули.

Алгоритм называется full, похожие на него называются A*, wave*.

Значит так, поехали:
1. Поставили в углу "2", если там "0". Вообще, в любом месте где можно поставить, поставили.
2. N = 3
3. Нашли на карте все значение равные N.
4. Окружили от по кругу значениями N+1. Можно в 4 стороны, можно в 8.
5. Если окружили хоть одну точку, то продолжаем с пункта 3, увеличив на N++.
6. Если нельзя окружить ни одной точки, то контур заполнен, увеличили счетчик количества откружение и переходим к пункту 1.
Как только не останется ни одной клетки с "0" -- выходим.

Начальное состояние:
11111
10001
10001
10001
11111

Заполненное:
11111
12341
13451
14561
11111

[LSL]

RomanPshenichny А можно в интернете
найти описание этого и подобных алгоритмов ?

В каких книгах есть ?

[RomanPshenichny]

> А можно в интернете найти описание этого и подобных
> алгоритмов ?

Видимо плохо объясняю

http://algolist.manual.ru/graphics/fill.php
http://doors.infor.ru/allsrs/alg/paper/2dgraph.html

А, вообще, любимый твой поисковик: "алгоритм заполнения области".
A*, wave* искать по "алгоритм поиска пути".

> В каких книгах есть ?

Сходу вспомнить в каких русских книжках есть такое сходу не берусь. В Graphics Gems есть точно.

[LSL]

RomanPshenichny Спасибо огромное !
Буду разбираться...