P13441 [GCJ 2009 #2] A Digging Problem

洞穴着火了，到处都是烟雾！你正试图挖掘一条通路，前往洞穴的底部，在那里你才能呼吸。问题在于，洞穴里有一些空气洞（空洞），你又不希望坠落得太深，否则会受伤。 洞穴被表示为一个 $R \times C$ 的矩阵，由空气洞和坚硬岩石单元格组成。你从位置 $(1, 1)$（即左上角）开始。你可以每次向左或向右移动一个单元格，前提是该单元格是空的（即空气洞）。移动之后，如果你下方的单元格是空气洞，你会一直下落，直到落到坚硬岩石上或洞穴底部为止。下落的距离不能超过 $F$，否则你会受伤。你必须在不受伤的情况下到达洞穴底部。下落过程中你不能左右移动。 你还可以“挖掘”，即将一个坚硬岩石单元格变为空气洞。你可以挖掘的单元格只能是你右下方或左下方的单元格。你挖掘的那个格子的上方必须是空气洞。在下落过程中你不能挖掘。 你的目标不仅是到达洞穴底部，还要尽可能少地进行挖掘。 让我们用一个具体的例子来描述操作过程：  - 你从 $(1, 1)$ 开始，向右移动 $3$ 次到达 $(1, 4)$，如图所示。 - 你挖掘了 $(2, 5)$ 位置的岩石，单元格 “A” 变为空气洞。 - 你向右移动一格，由于下方没有单元格，你会下落 $3$ 格到 $(4, 5)$。你挖掘 $(5, 6)$ 位置的岩石，单元格 “B” 变为空气洞。 - 你向右移动一格，由于下方没有单元格，你会下落 $1$ 格到 $(5, 6)$。 - 你已经通过挖掘 $2$ 个单元格到达了洞穴底部。

输入的第一行为一个整数 $N$，表示测试用例数量。接下来有 $N$ 组测试数据。每组测试数据的第一行为： $R\ C\ F$ 其中 $R$ 表示洞穴的行数，$C$ 表示洞穴的列数，$F$ 表示你能安全下落的最大距离。 接下来有 $R$ 行，每行含有 $C$ 个字符。每个字符可能为： - \# 表示坚硬岩石 - . 表示空气洞 左上角的单元格一定是空气洞，其下方的单元格一定是坚硬岩石。

对于每组测试数据，输出一行，格式如下： Case #X: No/Yes [D] 其中 $X$ 是测试编号（从 $1$ 开始）。如果你无法到达洞穴底部，输出 “No”；如果可以到达，输出 “Yes $D$”，其中 $D$ 是最少需要挖掘的单元格数。

**限制条件** - $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 完成。