AT_yuha_c83_01.Revenge of Voronoi - ボロノイの逆襲

“离散 Voronoi 图”是 Voronoi 图的一种变体。在离散 Voronoi 图中，图被表示为像素的集合。每个母点位于某些像素的中心，每个像素属于与其曼哈顿距离最近的母点。这里，曼哈顿距离是对于两个点 $(x_{1},\ y_{1})$ 和 $(x_{2},\ y_{2})$，由下式给出的距离。

你的任务是针对给定的离散 Voronoi 图，编写一个程序计算每个母点的坐标。在给定的离散 Voronoi 图中，每个母点用不同的小写英文字母表示。每个像素用其所属母点的字母表示。如果一个像素到多个母点的距离相同，则该像素属于这些母点中字母序最小的那个。

输入的第 $1$ 行包含两个整数 $W\ (1\leq W\leq 50)$ 和 $H\ (1\leq H\leq 50)$，分别表示离散 Voronoi 图的宽度和高度。接下来的 $H$ 行，每行包含 $W$ 个小写英文字母，每个字母表示一个像素。

请按照样例输出每个母点的坐标。每行输出一个母点的字母、X 坐标、Y 坐标。母点按字母顺序输出。坐标以左上角像素的中心为 $(0,0)$。

可以假定每个测试用例至少存在一个解。如果有多个解，输出任意一个均可。

• 仅当输入满足 $1\leq W,H\leq 8$ 时答对，得 $50$ 分。
• 仅当输入满足 $1\leq W,H\leq 16$ 时答对，得 $50$ 分。

第一行包含两个整数 $W$ 和 $H$，表示图的宽度和高度。

接下来的 $H$ 行，每行包含 $W$ 个小写英文字母，表示像素的归属。

对于每个母点，输出一行，包含母点的字母、X 坐标、Y 坐标。按字母顺序输出。

• 坐标以左上角像素的中心为 $(0,0)$。
• 如果有多个解，输出任意一个均可。
• 保证每个测试用例至少有一个解。

由 ChatGPT 4.1 翻译