Revenge of Voronoi
시간 제한8초메모리 제한512 MB
레이블이 붙은 격자가 주어질 때, 맨해튼 거리와 더 작은 문자 우선 규칙으로 같은 격자를 만드는 생성점의 위치를 찾는다.
문제
A discrete Voronoi diagram is a derivation of a Voronoi diagram. It is represented as a set of pixels. Each of the generatrices lies on the center of some pixel. Each pixel belongs to the generatrix nearest from the center of the pixel in the sense of Manhattan distance. The Manhattan distance d between two points (x1, y1) and (x2, y2) is given by the following formula:
d = |x1 - x2| + |y1 - y2|
Your task is to find a set of generatrices which generates a given discrete Voronoi diagram. In the given diagram, each generatrix is given a unique lowercase letter as its identifier, and each pixel is represented by the identifier of the generatrix the pixel belongs to. If a pixel has multiple generatrices at the same distance from its center, it belongs to the generatrix with the most preceding identifier among them (i.e. the smallest character code).
입력
The input consists of multiple test cases.
Each test case begins with a line containing two integers W (1 ≤ W ≤ 32) and H (1 ≤ H ≤ 32), which denote the width and height of the discrete Voronoi diagram.
The following H lines, each of which consists of W letters, give one discrete Voronoi diagram. Each letter represents one pixel.
The end of input is indicated by a line with two zeros. This is not a part of any test cases.
출력
For each test case, print the case number and the coordinates of generatrices as shown in the sample output. Each generatrix line should consist of its identifier, x-coordinate, and y-coordinate. Generatrices should be printed in alphabetical order of the identifiers. Each coordinate is zero-based where (0, 0) indicates the center of the top-left corner pixel of the diagram.
You may assume that every test case has at least one solution. If there are multiple solutions, any one is acceptable.
Print a blank line after every test case including the last one.