Revenge of Voronoi

Revenge of Voronoi

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 (1W32) and H (1H32), 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.

Time limit 10 seconds
Memory limit 64 MiB
Input example #1
4 3
4 1
4 4
0 0
Output example #1
Case 1:
o 0 0
x 2 0

Case 2:
l 2 0
n 0 0
u 1 0

Case 3:
a 0 0
b 2 0
c 0 2
d 2 2