Description

你正站在珠穆朗玛峰的山坡上。你需要在冻僵之前找到一个避难所，而现在天已经黑了！你该怎么办？

好消息是，你已经记住了整座山的布局。这是一张网格图，其中有些格子无法通过，另一些格子包含可以过夜的山洞。坏消息是，你并不知道自己所在的位置，并且由于坡度太陡，你无法往上爬。你只能向左、右或向下移动。

下面是一个布局示例，'.' 表示可通行的格子，'#' 表示不可通行的格子，数字表示山洞：

######
##...#
#..#.#
#...##
#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" 能保证从这些格子的任意一个出发，最终都停在该山洞。

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据，每组首先一行两个整数 $\mathbf{R}$ 和 $\mathbf{C}$，表示山的行数和列数。

接下来有 $\mathbf{R}$ 行，每行 $\mathbf{C}$ 个字符，描述山的布局。与上例一样，'#' 表示不可通行的格子，'.' 表示可通行的格子，'0'-'9' 表示山洞（也是可通行的格子）。

Output Format

对于每个测试用例，首先输出一行 "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"，如上所述。

2
7 5
#####
##0##
##1.#
##2##
#3..#
#.#.#
#####
7 6
######
##...#
#..#.#
#...##
#0#..#
####1#
######

Case #1:
0: 1 Lucky
1: 3 Lucky
2: 4 Unlucky
3: 7 Lucky
Case #2:
0: 9 Lucky
1: 11 Unlucky

Hint

样例说明

在第一个样例中，下面是一些对 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 完成。