Histology Outline Tracer

A stained tissue sample is represented as a bitmap whose pixels are either stained or unstained. Find every connected region of stained pixels and, for each region with at least the required minimum number of pixels, output its outer outline. Regions smaller than the minimum are ignored. Boundaries of holes inside a region are not output; only the outside outline is followed.

A pixel is adjacent to the pixel directly above, below, left, or right of it. Two stained pixels are connected if there is a sequence of stained pixels from one to the other where consecutive pixels are adjacent. A stained region is a set of stained pixels all connected to one stained pixel. A stained pixel is a boundary pixel of its region if at least one of its four adjacent positions is unstained or outside the bitmap. Every position immediately outside the bitmap is considered unstained.

An outline starts at the leftmost boundary pixel on the topmost row of the region. Then follow the boundary pixels clockwise, writing the direction code for each move to the next boundary pixel.

H A B
G   C
F E D

Rows are numbered from top to bottom starting at 1. Columns are numbered from left to right starting at 1.

The input is a sequence of problem instances. Each instance begins with one line containing three integers: row-count, column-count, and minimum-number-of-pixels. It is followed by row-count lines, each containing column-count characters. A period (.) is an unstained pixel, and an uppercase X is a stained pixel. The input ends when row-count is 0.

row-count is at most 47, column-count is at most 63, and minimum-number-of-pixels is at least 2.

For each instance, first output one line containing the number of stained regions with at least the minimum number of pixels. Then output the outline description for each such region. Regions are listed in the order in which the first pixel of the region appears when scanning rows from top to bottom and, within a row, from left to right.

For each region, output one line with the row number of the start pixel, the column number of the start pixel, and the number of outline direction codes, separated by single spaces. Then output the outline string using direction codes A through H. Every outline line except the last must contain exactly 40 characters.