P13327 [GCJ 2012 #2] Descending in the Dark

你正站在珠穆朗玛峰的山坡上。你需要在冻僵之前找到一个避难所，而现在天已经黑了！你该怎么办？ 好消息是，你已经记住了整座山的布局。这是一张网格图，其中有些格子无法通过，另一些格子包含可以过夜的山洞。坏消息是，你并不知道自己所在的位置，并且由于坡度太陡，你无法往上爬。你只能向左、右或向下移动。 下面是一个布局示例，'.' 表示可通行的格子，'#' 表示不可通行的格子，数字表示山洞： ``` ###### ##...# #..#.# #...## #0#..# ####1# ###### ``` 由于天太黑了，你只能按照一个*计划*行动，这是一串指令，每条指令都让你向左、右或下移动一格。如果某条指令会让你走到一个可通行的格子或山洞，你就执行它。如果会走到一个不可通行的格子，你就必须忽略这条指令。不论是否执行，你都会继续下一步，直到计划全部执行完毕。 为了帮助你下山，你希望对每个山洞 $\mathbf{C}$ 得到两个信息： * 可以从哪些格子到达山洞 $\mathbf{C}$？我们用 $\mathbf{S}_{\mathbf{C}}$ 表示这些格子的集合，$\mathbf{n}_{\mathbf{C}}$ 表示这些格子的数量。 * 是否存在一个计划，使得从 $\mathbf{S}_{\mathbf{C}}$ 的任意一个格子出发，最终都能到达山洞 $\mathbf{C}$？如果存在，我们称该山洞是**Lucky** 的。 注意，在按计划行动的过程中，你可能会经过多个山洞。唯一重要的是你最终**停留**在哪个格子，而不是途中经过了哪些山洞。 例如，在上面的布局中，山洞 0 是 Lucky 的。有 9 个格子可以到达它（包括它本身），计划 "left-left-down-down-down-left-down" 能保证从这些格子的任意一个出发，最终都停在该山洞。

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据，每组首先一行两个整数 $\mathbf{R}$ 和 $\mathbf{C}$，表示山的行数和列数。 接下来有 $\mathbf{R}$ 行，每行 $\mathbf{C}$ 个字符，描述山的布局。与上例一样，'#' 表示不可通行的格子，'.' 表示可通行的格子，'0'-'9' 表示山洞（也是可通行的格子）。

对于每个测试用例，首先输出一行 "Case #$x$:"，其中 $x$ 为测试用例编号（从 1 开始）。对于每个山洞 $\mathbf{C}$（从 0 开始递增），输出一行 "$\mathbf{C}$: $\mathbf{n}_{\mathbf{C}}$ $\mathbf{L}_{\mathbf{C}}$"。其中 $\mathbf{C}$ 是山洞编号，$\mathbf{n}_{\mathbf{C}}$ 是能到达该山洞的格子数，$\mathbf{L}_{\mathbf{C}}$ 为 "Lucky" 或 "Unlucky"，如上所述。

**样例说明** 在第一个样例中，下面是一些对 Lucky 山洞可用的计划： - 对于山洞 0，可以使用空计划。如果你能到达该山洞，说明你已经在正确的位置！ - 对于山洞 1，可以使用计划 right-down-left。 - 对于山洞 3，可以使用计划 right-right-left-down-down-down-left。 **限制条件** - 山洞数量在 1 到 10 之间。 - 若有 $d$ 个山洞，则编号为 $\{0, 1, \ldots, d-1\}$，且不会有重复编号。 - 山的布局边界上的所有格子都是不可通行的。 - $1 \leq T \leq 20$ **测试集 1（8 分，结果可见）** - $3 \leq R, C \leq 10$ **测试集 2（30 分，结果隐藏）** - $3 \leq R, C \leq 60$ 翻译由 ChatGPT-4.1 完成。