P9450 [ICPC 2021 WF] Where Am I?

我是谁？我是什么？我为什么存在？这些都是让哲学家们在过去的千年里一直忙碌的问题。但是当谈到“我在哪里”时，现代智能手机和 GPS 卫星几乎已经让这个问题失去了吸引力。 为了给那些曾经思考“我在哪里”问题的空间哲学家们再添一层伤害，“即时制图定位公司”（ICPC）决定进行一次演示，以展示 GPS 比传统地图强大得多。他们的论点是，地图只有在你已经知道自己在哪里时才有用，但如果你从一个未知位置开始，地图的用处就小得多了。 在这次演示中，ICPC 创建了一个测试区域，该区域被布置成一个无限的笛卡尔网格。大多数网格单元是空的，但有限数量的单元在其中心有一个标记（参见图 L.1(a) 中的五个标记单元的示例）。所有空网格单元看起来都一样，所有带标记的单元也看起来都一样。假设你得到了测试区域的地图（即所有标记的位置），并且你被放置在一个（你不知道的）网格单元上。你需要多长时间才能找到你实际所在的位置？ICPC 的答案很明确：可能需要很长很长的时间，而 GPS 会立即给你答案。但究竟需要多长时间呢？  在试验中，测试对象将通过遵循一个顺时针扩展的螺旋形来探索他们的环境，其前几步如图 L.1(b) 所示。起始单元标记为“0”，数字显示了访问其他单元的顺序。测试对象只有在其网格单元上才能看到标记，并且一旦他们根据迄今为止看到的网格单元知道自己在哪里，他们就会停止探索。这意味着观察到的空和标记网格单元的序列只能从一个可能的起始位置开始。网格是无限的，但探索将是有限的，因为一旦测试对象看到了网格上的所有标记，他们就一定知道自己在哪里。 让数百名测试对象字面意义上地绕圈跑可能会很昂贵，所以 ICPC 认为编写一个模拟程序会更便宜更快。也许你可以帮忙？

输入描述一个单一的网格。首先是一行包含两个整数 $d_x$ 和 $d_y$ ($1 \leq d_x, d_y \leq 100$)。接下来的 $d_y$ 行每行包含 $d_x$ 个字符，描述测试网格的一部分。网格描述的第 $j$ 行的第 $i$ 个字符指定了坐标 ($i$, $d_y-j+1$) 处网格单元的内容。字符要么是 '$\texttt{.}$'，要么是 '$\texttt{X}$'，分别表示单元是空的或者包含一个标记。 网格中的标记总数将在 $1$ 到 $100$ 之间（含）变化。输入描述范围之外的所有网格单元都是空的。

在 ICPC 的实验中，测试对象知道他们将从某个位置 ($x$, $y$) 开始，其中 $1 \leq x \leq d_x$，$1 \leq y \leq d_y$。 输出三行。第一行应包含识别起始位置所需的期望步数，假设起始位置是均匀随机选择的。这个数字需要精确到绝对误差 $10^{-3}$ 以内。 第二行应包含识别起始位置所需的最大步数。 第三行应列出所有需要最大步数的起始坐标 ($x$, $y$)。坐标应按 $y$ 坐标递增排序，如果 $y$ 坐标相同，则按 $x$ 坐标递增排序。

题面翻译由 ChatGPT-4o 提供。