Description

洞穴着火了，到处都是烟雾！你正试图挖掘一条通路，前往洞穴的底部，在那里你才能呼吸。问题在于，洞穴里有一些空气洞（空洞），你又不希望坠落得太深，否则会受伤。

洞穴被表示为一个 $R \times C$ 的矩阵，由空气洞和坚硬岩石单元格组成。你从位置 $(1, 1)$（即左上角）开始。你可以每次向左或向右移动一个单元格，前提是该单元格是空的（即空气洞）。移动之后，如果你下方的单元格是空气洞，你会一直下落，直到落到坚硬岩石上或洞穴底部为止。下落的距离不能超过 $F$，否则你会受伤。你必须在不受伤的情况下到达洞穴底部。下落过程中你不能左右移动。

你还可以“挖掘”，即将一个坚硬岩石单元格变为空气洞。你可以挖掘的单元格只能是你右下方或左下方的单元格。你挖掘的那个格子的上方必须是空气洞。在下落过程中你不能挖掘。

你的目标不仅是到达洞穴底部，还要尽可能少地进行挖掘。

让我们用一个具体的例子来描述操作过程：

• 你从 $(1, 1)$ 开始，向右移动 $3$ 次到达 $(1, 4)$，如图所示。
• 你挖掘了 $(2, 5)$ 位置的岩石，单元格 “A” 变为空气洞。
• 你向右移动一格，由于下方没有单元格，你会下落 $3$ 格到 $(4, 5)$。你挖掘 $(5, 6)$ 位置的岩石，单元格 “B” 变为空气洞。
• 你向右移动一格，由于下方没有单元格，你会下落 $1$ 格到 $(5, 6)$。
• 你已经通过挖掘 $2$ 个单元格到达了洞穴底部。

Input Format

输入的第一行为一个整数 $N$，表示测试用例数量。接下来有 $N$ 组测试数据。每组测试数据的第一行为：

$R\ C\ F$

其中 $R$ 表示洞穴的行数，$C$ 表示洞穴的列数，$F$ 表示你能安全下落的最大距离。

接下来有 $R$ 行，每行含有 $C$ 个字符。每个字符可能为：

• # 表示坚硬岩石
• . 表示空气洞

左上角的单元格一定是空气洞，其下方的单元格一定是坚硬岩石。

Output Format

对于每组测试数据，输出一行，格式如下：

Case #X: No/Yes [D]

其中 $X$ 是测试编号（从 $1$ 开始）。如果你无法到达洞穴底部，输出 “No”；如果可以到达，输出 “Yes $D$”，其中 $D$ 是最少需要挖掘的单元格数。

3
2 2 1
.#
##
3 3 1
...
###
###
3 2 1
..
#.
..

Case #1: No
Case #2: Yes 3
Case #3: No

Hint

限制条件

• $1 \leq N \leq 50$
• $1 \leq F < R$

小数据集

• 时间限制：4 秒
• $2 \leq R \leq 10$
• $2 \leq C \leq 6$

大数据集

• 时间限制：6 秒
• $2 \leq R \leq 50$
• $2 \leq C \leq 50$

翻译由 ChatGPT-4.1 完成。