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:
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).
Input
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.
Output
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.
Example
Input: 4 3 ooxx ooxx ooxx 4 1 null 4 4 aabb aabb ccdd ccdd 0 0 Output: 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
hide comments
Tony Beta Lambda:
2010-06-29 08:00:24
I mistakenly deleted Lordxfastx's comment. The original text was:
|
|
[Trichromatic] XilinX:
2009-09-24 12:08:27
Added some new test data :-) |
Added by: | Bin Jin |
Date: | 2008-09-08 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | JAG wintercamp 08, day2 |