윤곽선 추적

컴퓨터 비전에서 관심 대상 물체는 흔히 이진 영상(비트맵)에서 값이 1인 화소들의 영역으로 표현된다. 물체를 식별하는 중요한 과정 중 하나는 물체의 윤곽선(경계선이라고도 한다)을 추적하는 것이다.

비트맵의 가장자리에는 값이 1인 화소가 없다고 가정한다. 하나의 물체의 윤곽선은 다음의 무어(Moore) 경계 추적 알고리즘으로 추적한다.

1. 비트맵을 위쪽 행부터 아래쪽 행까지, 각 행에서는 왼쪽에서 오른쪽으로 훑어 처음으로 만나는 물체 화소를 찾는다. 이 화소를 $b_0$라 하고, 그 서쪽(왼쪽) 배경 이웃을 $c_0$라 한다.
2. $c_0$에서 시작하여 시계 방향으로 $b_0$의 8개 이웃을 살핀다. 처음으로 만나는 물체 화소를 $b_1$이라 하고, $b_1$ 바로 직전에 살핀 배경 이웃을 $c_1$이라 한다. $b_0$과 $b_1$을 윤곽선에 추가한다.
3. $b = b_1$, $c = c_1$로 둔다.
4. $c$에서 시작하여 시계 방향으로 $b$의 8개 이웃을 $n_1, n_2, \dots, n_8$이라 하고, 이 순서에서 처음으로 나오는 물체 화소를 $n_k$라 한다.
5. $b = n_k$, $c = n_{k-1}$로 두고, $b$를 윤곽선에 추가한다.
6. $b = b_0$이 되고 다음으로 찾은 윤곽선 화소가 $b_1$이 될 때까지 4번과 5번을 반복한다. 이 마지막의 $b_0$, $b_1$은 시작 부분이 반복된 것이므로 다시 추가하지 않는다.

최대 200개의 행과 200개의 열을 가진 비트맵이 주어지며, 그 안에는 여러 개의 물체가 있다. 각 물체에 대해 위 절차로 윤곽선의 길이(추적된 윤곽선에 포함된 화소의 개수)를 구하여라.

화소 값 0은 배경, 1은 물체 화소를 뜻한다. 두 물체 화소는, 8방향(상하좌우와 대각선) 중 어느 방향으로든 이동하는 물체 화소들의 경로로 이어져 있으면 같은 물체에 속한다. 비트맵의 가장자리(첫 행, 마지막 행, 첫 열, 마지막 열)는 항상 배경이다. 화소가 5개 미만인 물체는 잡음으로 보아 무시한다. 어떤 물체에도 구멍은 없다. 달리 말해, 임의의 두 배경 화소는 상하좌우 4방향만으로 이동하는 배경 화소들의 경로로 항상 이어져 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 두 양의 정수 $R$과 $C$가 적힌 줄로 시작하며, 각각 비트맵의 행 수와 열 수이다. 이어지는 $R$개의 줄에는 각각 0 또는 1로 이루어진 길이 $C$의 문자열이 주어진다. 입력은 $R = C = 0$인 케이스로 끝나며, 이 마지막 케이스는 처리하지 않는다.

각 케이스마다 케이스 번호를 한 줄에 Case k 형식으로 출력한다. 다음 줄에는 비트맵에서 찾은 모든 물체의 윤곽선 길이를 오름차순으로 정렬하여 공백 하나로 구분해 출력한다. 화소가 5개 이상인 물체가 하나도 없으면, 그 줄에 no objects found를 대신 출력한다.