SP3009 VORONOI - Revenge of Voronoi

离散 Voronoi 图是一种像素化的 Voronoi 图，定义为一组像素，其中每个生成点（生成器）位于某个像素的中心。每个像素属于其中心到生成器的曼哈顿距离最近的生成器。两个点 (_x_ $_{1}$, _y_ $_{1}$) 和 (_x_ $_{2}$, _y_ $_{2}$) 之间的曼哈顿距离 _d_ 计算方式如下： _d_ = |_x_ $_{1}$ - _x_ $_{2}$| + |_y_ $_{1}$ - _y_ $_{2}$| 你的任务是找出一组生成器，它们能生成给定的离散 Voronoi 图。在这个图中，每个生成器用一个独特的小写字母标识，每个像素用所属生成器的标识符表示。如果一个像素到多个生成器的距离相等，它将属于标识符字母序列较前的生成器。

输入由多组测试用例组成。 每个测试用例以一行包含两个整数 _W_ (1 ≤ _W_ ≤ 32) 和 _H_ (1 ≤ _H_ ≤ 32) 开始，表示离散 Voronoi 图的宽度和高度。 接下来 _H_ 行，每行包含 _W_ 个字母，表示一个离散 Voronoi 图。每个字母代表一个像素所属的生成器。 输入以一行两个零结束，表示输入结束，不属于任何测试用例的数据。

对于每个测试用例，输出该用例的编号以及生成器的坐标，格式需参考样例输出。每行输出一个生成器的信息，包括其标识符、_x_ 坐标和 _y_ 坐标。生成器需要按照标识符的字母顺序输出。坐标是从零开始计数的，其中 (0, 0) 表示图的左上角像素的中心。 可以确保每个测试用例至少有一个有效方案。如果存在多个方案，输出任意一个都可以。 每个测试用例输出后请留一个空行，即使是最后一个用例也是如此。 **本翻译由 AI 自动生成**