← 返回题目列表

AtCoder · yuha_c83_01

A. 沃罗诺伊的复仇 - 沃罗诺伊的复仇

中文机器翻译题面 查看原题

問題文

“离散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 积分

入力例 1

4 3
ooxx
ooxx
ooxx

出力例 1

o 0 0
x 2 0

入力例 2

4 1
null

出力例 2

l 2 0
n 0 0
u 1 0

入力例 3

4 4
aabb
aabb
ccdd
ccdd

出力例 3

a 0 0
b 2 0
c 0 2
d 2 2