Что значит граничить
Либо они окружены единицами либо нет
А вообще можно так: ищем (перебором) ноль
далее рекурсивно налево, направо, вверх, вниз смотрим что там. Есть два варианта - либо область нулей ограничена 1 либо она касается границы. Т.о. рекурсивная функция:
1) Возвращает 1 если встретила на пути единицу
2) Возвращает 0 если встретила на пути границу массива
3) Если на вызванном месте 0, то возвращает 0 если возвратила 0 одна из вызванных соседних клеток, иначе - 1
Ну и чтобы не зациклица проверенные места надо вычеркивать. Ну и нули считать по ходу дела.
Надеюсь понятно [Ответ]
LSL 15:22 28.05.2003
vicmb
Да. В примере видно...
Spectator
Что значит граничить
Либо они окружены единицами либо нет
Я имел в виду что окружённых областей может быть несколько.
Они могут граничить ,перекрывать друг друга.
Или быть одна в другой !
Так вот надо посчитать окружённые нули во всех областях.
такое же задание(почти) на олимпиаде по информатике (10 класс) было - я решил тогда, правда как не помню.(помню брал любую единицу и двигался по соседним единицам в какую то сторону до тех пор пока не возвращался на исходное "1"-это и есть замкнутый круг) больше ничего не помню. кстати я тогда решил её(только её) и получил 3 место(там она чють попроще была).
-----------------------------
Может натолкнул на мысль?
Если нет - извиняйте.
[Ответ]
Spectator 11:48 29.05.2003
zerg
Тоже вариант
При этом надо отмечать пройденные 1 по ходу и если круг замкнулся то сканированием (слева направо сверху вниз) посчитать количество 0 внутри
только от рекурсии все равно не уйдешь. Так как внутри каждого круга может быть еще один круг - тогда это будет две разных области и рекурсия вообще будет сложнее (надо передавать внутрь маску в которой надо искать 1 и круг образованный этими единицами).
Т.о. отталкиваться можно и от единиц (как у zerg) и от нулей (как у меня). Мой алгоритм чуть сложнее понять, но реализация представляется мне проще. Если реализовывать по моему хватит одной булевой матрицы (глобальной), а у zerg - несколько (передающихся в рекурсию).
Может я и не прав, я не оправдываю свой вариант, а токмо хочу помочь LSL.
[Ответ]
LSL 17:25 29.05.2003
zerg Spectator это и есть замкнутый круг
Ну и что ? А как теперь в нём нули посчитать...
если круг замкнулся
Беда в том что "круг" может граничить с другими..
То есть как его обойти, если стенки расходиться будут ?
Как на примере...
сканированием (слева направо сверху вниз)
А если "круг" неправильный ? Внутрь вогнутый...
Как на примере...
Наверно я чего-то не понимаю...
А давайте-ка исходники в форум!
И сразу понятно будет...
Сделай волновым алгоритмом - ищеш выход, если нет то все ок.
Волновой алгоритм состоит в пуске волны распространяющейся во все стороны (помечается область, где мы уже были). Ищется кратчайший путь, но тебе достачно выяснить, что его нет
[Ответ]
Spectator 19:25 29.05.2003
Bias
А я что написал? Просто сами мы неграмотные, в университетах не учились Про то, что это волновой алгоритм не знаем (иш ты як москали перебор с рекурсией называют
LSL:
>>это и есть замкнутый круг
>Ну и что ? А как теперь в нём нули посчитать...
Я сказал сверху вниз, слева направо if 0 then cnt++
>>если круг замкнулся
>Беда в том что "круг" может граничить с другими..
>То есть как его обойти, если стенки расходиться будут ?
>Как на примере...
Дык я же говорю - на примере у нас есть круг и в нем еще круг - то что стенки совпадают - не беда, все равно он вложенный. Представь попу - т. е. круг разделенный линией. Мы нашли внешний круг вместе с разделающей линией. Потом внутре ищем более меньший круг, не совпадающий по всем точкам со внешним. Я уже сказал что рекурсия будет непростой.
>>сканированием (слева направо сверху вниз)
>А если "круг" неправильный ? Внутрь вогнутый...
>Как на примере...
Ну и что. Есть такая задача - лежит ли точка внутри фигуры? Ответ - надо пустить луч из бесконечности в эту точку по любой прямой (на практике пускают луч по прямой паралельной оси X или Y из точки за пределами фигуры). Если этот луч пересекает стенки фигуры четное число раз - значит точка за пределами фигуры. Иначе - внутре. Причем фигура может быть и впуклой. Главное, чтобы замкнутая. Намек понял?
>А давайте-ка исходники в форум!
Облезешь, неровно обрастешь Некрасивым станешь
>И сразу понятно будет...
>Кто у нас лучший кодер ?
Конечно же ты [Ответ]
RomanPshenichny 23:00 29.05.2003
> Некоторая область нулей "окружена" единицами.
> Областей может быть несколько и они могут граничить
> друг с другом.
> Нужно подсчитать "окружённые" нули.
Алгоритм называется full, похожие на него называются A*, wave*.
Значит так, поехали:
1. Поставили в углу "2", если там "0". Вообще, в любом месте где можно поставить, поставили.
2. N = 3
3. Нашли на карте все значение равные N.
4. Окружили от по кругу значениями N+1. Можно в 4 стороны, можно в 8.
5. Если окружили хоть одну точку, то продолжаем с пункта 3, увеличив на N++.
6. Если нельзя окружить ни одной точки, то контур заполнен, увеличили счетчик количества откружение и переходим к пункту 1.
Как только не останется ни одной клетки с "0" -- выходим.
