問題文
“离散Voronoi图”是Voronoi图的一种变体。在离散Voronoi图中,图被表示为像素的集合。每个母点位于若干像素的中心,每个像素属于在曼哈顿距离上最近的母点。这里的曼哈顿距离是两个点
(x_{1}, y_{1})
和
按字典顺序比较
(x_{2}, y_{2})
是通过以下公式给出的距离。
d = |x_{1} - x_{2}| + |y_{1} - y_{2}|
你的工作是针对给定的离散沃罗诺伊图,编写一个计算每个母点坐标的程序。
在给定的离散沃罗诺伊图中,每个母点用不重复的小写英文字母表示。每个像素则用该像素所属的母点字母表示。
如果一个像素与多个母点等距,该像素属于字母顺序最小的母点。
入力
输入的第一行包含两个整数,
W (1 ≤ W ≤ 50)
和
按字典顺序比较
H (1 ≤ H ≤ 50)
分别表示离散沃罗诺伊图的宽度和高度。接下来
H
行包含
W
包含小写英文字母,每个字母表示一个像素。
出力
按示例输出中所示的格式输出母点的坐标。每行由母点的小写字母、X坐标、Y坐标组成。
母点应按所代表的小写字母的字母顺序输出。坐标为
(0,0)
以左上角像素的中心为准。对于每个测试用例,可以假设至少存在一个解。另,如果存在多个解,可以输出任意一个。
部分点
- 1 ≤ W, H ≤ 8 的输入给出正确答案,则部分点为 50
积分
- 1 ≤ W, H ≤ 16 的输入给出正确答案,则部分点为 50
积分