seuOJ207 - 挖岩石

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：8500 ms
• 空间限制：256 MiB
• 题目标签：夏季, 校赛, 2019

题目描述

在一个二维世界中，你操作一个人进行探险，来到一个奇怪的地方，你站在岩石上，需要到地面上去。地图是个 $N\times M$ 的矩阵，左上角为 $(1,1)$，右下角为 $(N,M)$，矩阵中每一项为空格或岩石，地面是第 $N$ 层格子的底线（或者你也可以理解为第 $N+1$ 层是地面）。你只能站在岩石或地面上。

你可以在这个世界里移动。当你位于 $(x,y)$ 时，如果 $(x,y-1)$ 是空格，$(x+1,y-1)$ 是岩石，那你就可以从 $(x,y)$ 移动到 $(x,y-1)$；同样的，如果 $(x,y+1)$ 是空格，$(x+1,y+1)$ 是岩石，那你就可以从 $(x,y)$ 移动到 $(x,y+1)$。

你可以在这个世界里竖直落体。当你位于 $(x,y)$ 时，如果 $(x,y-1)$ 和 $(x+1,y-1)$ 是空格，就可以从 $(x,y-1)$ 处竖直下落，并持续下落直到碰到地面或岩石；同样的，如果 $(x,y+1)$ 和 $(x+1,y+1)$ 是空格，就可以从 $(x,y+1)$ 处竖直下落。但由于下落的距离（定义为坐标中第一项变换量的绝对值）过大会摔伤，所以你下落的距离不能超过 $R$。例如，你从 $(x,y)$ 下落到 $(x',y)$，那么你下落的距离就是 $x'-x$。

同时你有一个技能可以挖走一块岩石。当你位于 $(x,y)$ 时，如果 $(x,y-1)$ 是空格，$(x+1,y-1)$ 是岩石，就可以挖走 $(x+1,y-1)$ 处的岩石；同样的，如果 $(x,y+1)$ 是空格，$(x+1,y+1)$ 是岩石，就可以挖走 $(x+1,y+1)$ 处的岩石，使其变为空格。每次你使用这个技能体能就会消耗 $1$，当然下落的过程中是不能挖岩石的。挖完岩石后你还是处于原地。

要注意的是，以上操作（移动、下落、挖岩石）都必须是在地图范围内。

你想知道你最少消耗多少体能才能到地面，即你需要达到最下一层的空格处。

一开始你在矩阵的左上角，数据保证此时你脚下一定是岩石。

例如上图，你从 $(1,1)$ （左上角）出发，走到 $(1,4)$（你现在所在的格子为 $(1,4)$，脚下的格子为 $(2,4)$），如果你挖去右下方的岩石 $(2,5)$，A 就消失。此时你向右走会下落 $3$ 格到 $(4,5)$，你再消去 $(5,6)$ 并向右走就到了地面。总共消耗的体能是 $2$。

输入格式

输入数据第一行一个数 $T(1\leq T\leq 5)$，表示数据组数。

对于每组测试数据，第一行三个数 $N,M,R(0\leq N,M,R\leq 50)$，分别表示地图的大小（$N\times M$），$R$ 表示最大下落距离。接下来 $N$ 行 $M$ 列由 . 与 # 组成的矩阵表示地图，其中第 $i$ 行 $j$ 列为 . 则表示位置 $(i,j)$ 为空格，否则为岩石。

输出格式

对于每组测试数据请输出一行一个字符串。

• 如果对应该组测试数据你可以到达地面请输出字符串 "Yes {consume}"，其中 {consume} 应替换为一个整数，表示最小消耗的体能。
• 如果对应该组测试数据你不能到达地面请输出字符串 "No"。

样例

样例输入

3
5 8 3
........
########
...#.###
####..##
###.##..
2 2 1
.#
##
3 3 1
...
###
###

样例输出

Yes 2
No
Yes 3