조직 표본 윤곽 추적
시간 제한1초메모리 제한128 MB
비트맵에서 연결된 염색 영역들을 찾아 최소 크기 이상인 것만 시계방향 8방향 코드로 외곽선을 추적해 출력하는 문제입니다.
문제
염색된 조직 표본의 디지털 현미경 사진은 각 픽셀이 염색되었는지 아닌지로 표현된다. 프로그램은 염색된 픽셀들의 연결 영역을 찾고, 지정된 최소 픽셀 수 이상인 각 영역에 대해 바깥쪽 윤곽을 출력해야 한다. 최소 픽셀 수보다 작은 영역은 무시한다. 내부 구멍의 경계는 출력하지 않으며, 각 영역의 외곽만 따른다.
한 픽셀은 바로 위, 바로 아래, 바로 왼쪽, 바로 오른쪽에 있는 픽셀과 인접한다. 두 염색 픽셀 사이에 인접한 염색 픽셀들의 연속된 경로가 있으면 두 픽셀은 연결되어 있다. 염색 픽셀들의 영역은 하나의 염색 픽셀과 모두 연결된 염색 픽셀들의 집합이다. 어떤 염색 픽셀의 상하좌우 이웃 중 하나 이상이 염색되지 않았거나 비트맵 밖이면, 그 픽셀은 해당 영역의 경계 픽셀이다. 비트맵 바로 바깥의 픽셀은 모두 염색되지 않은 것으로 본다.
윤곽은 그 영역에서 가장 위쪽 행에 있는 경계 픽셀 중 가장 왼쪽 픽셀에서 시작한다. 이후 경계 픽셀들을 시계 방향으로 따라가며, 다음 경계 픽셀로 이동하는 방향을 다음 코드로 기록한다.
H A B
G C
F E D
행 번호는 위에서 아래로 1부터 세고, 열 번호는 왼쪽에서 오른쪽으로 1부터 센다.
입력
입력은 여러 개의 문제 인스턴스로 이루어진다. 각 인스턴스는 세 정수 row-count, column-count, minimum-number-of-pixels가 있는 한 줄로 시작한다. 이어서 row-count개의 줄이 주어지며, 각 줄은 column-count개의 문자로 이루어진다. 마침표(.)는 염색되지 않은 픽셀, 대문자 X는 염색된 픽셀을 뜻한다. row-count가 0이면 입력이 끝난다.
row-count는 최대 47, column-count는 최대 63이며, minimum-number-of-pixels는 2 이상이다.
출력
각 인스턴스마다 먼저 최소 픽셀 수 이상인 염색 영역의 개수를 한 줄에 출력한다. 이어서 각 영역의 윤곽 설명을 출력한다. 영역들은 위에서 아래로, 같은 행에서는 왼쪽에서 오른쪽으로 비트맵을 훑을 때 그 영역의 첫 픽셀이 처음 나타나는 순서대로 출력한다.
각 영역에 대해 첫 줄에는 시작 픽셀의 행 번호, 열 번호, 윤곽 이동 코드의 개수를 공백 하나로 구분해 출력한다. 다음 줄들에는 방향 코드 A부터 H까지로 이루어진 윤곽 문자열을 출력한다. 마지막 줄을 제외한 각 윤곽 문자열 줄은 정확히 40글자여야 한다.