Обводка контура
В области компьютерного зрения объекты на бинарном изображении часто представлены как области, заполненные 1. Одной из ключевых задач при идентификации таких объектов является определение их контура, или границы.
Предположим, что на границах битмапы отсутствуют 1. Для отслеживания контура одного объекта можно воспользоваться алгоритмом отслеживания границы Мура, который выполняется следующим образом:
Просматривайте изображение сверху вниз и слева направо, пока не обнаружите пиксель объекта. Обозначьте этот пиксель как b0, а его западного соседа по фону как c0.
Исследуйте 8 соседей b0, начиная с c0 и двигаясь по часовой стрелке. Обозначьте первый найденный соседний пиксель объекта как b1, а сосед по фону, непосредственно предшествующий b1, как c1. Запомните координаты b0 и b1, добавив их к контуру.
Установите b = b1 и c = c1.
Рассмотрите 8 соседей b, начиная с c и двигаясь по часовой стрелке, обозначив их как n1, n2, ..., n8. Найдите первого соседа объекта nk в этой последовательности.
Установите b = nk, c = n(k-1). Добавьте b к контуру.
Повторяйте шаги 4 и 5, пока b = b0 и следующий найденный контурный пункт не будет b1. Последние два пункта b0 и b1 повторяются и не должны быть добавлены к контуру снова.
Начальные шаги алгоритма иллюстрируются на рисунке ниже (только пиксели на границе отмечены 1 в этой битмапе):
В этой задаче вам будет предоставлена битмапа размером не более 200 строк и 200 столбцов. Битмапа может содержать несколько объектов. Ваша задача — определить длину контура каждого объекта в битмапе, используя описанную выше процедуру. В битмапе пиксели с интенсивностью 0 представляют фон, а пиксели с интенсивностью 1 — пиксели объекта. Два пикселя с интенсивностью 1 принадлежат одному объекту, если существует путь между ними, состоящий только из 1, и путь может следовать в любом из 8 направлений компаса. Границы битмапы (первая и последняя строки, первый и последний столбцы) содержат только фоновые пиксели. Объекты, состоящие из менее чем 5 пикселей, следует игнорировать, так как они, вероятно, являются шумом. Ни один из объектов в битмапе не имеет дыр. Это эквивалентно тому, что существует путь из фоновых пикселей, следуя только 4 основным направлениям компаса (С, Ю, В, З) для каждой пары фоновых пикселей в битмапе.
Входные данные
Входные данные состоят из нескольких случаев. Каждый случай начинается с двух положительных целых чисел на одной строке, указывающих количество строк (R) и количество столбцов (C) в битмапе. Битмапа представлена в следующих R строках, каждая из которых содержит строку из 0 и 1 длиной C. Ввод завершается случаем, начинающимся с R = C = 0. Последний случай не должен обрабатываться.
Выходные данные
Для каждого случая выведите номер случая на отдельной строке. На следующей строке выведите длины контуров всех объектов, найденных в битмапе, отсортированные в порядке возрастания. Разделите длины контуров одним пробелом на этой строке. Если в битмапе нет объектов, содержащих как минимум 5 пикселей, выведите строку 'no objects found'.