SP3920 BYTESE1 - Lucius Dungeon

在一个地牢中，有一些房间组成了一个 $M \times N$ 的矩形网格。邪恶的卢修斯·马尔福因为憎恨麻瓜出身的人，把赫敏囚禁在了其中一间房间里。勇敢的哈利·波特正在赶来营救赫敏。他从网格的左上角房间 $(1,1)$ 开始，每个房间里有一些守卫，哈利需要花一些时间去消灭这些守卫。消灭守卫所需的时间因房间不同而不同。消灭完一个房间的守卫后，哈利可以向左、右、上或下移动到相邻的房间，但不能对角线移动。 卢修斯·马尔福知道哈利·波特已在路上，于是设了一个定时炸弹，准备在 $T$ 秒后引爆，威胁到赫敏的生命。你将得到赫敏所在房间的位置、炸弹爆炸前的剩余时间，以及哈利在每个房间消灭守卫需要的时间，任务是判断哈利是否能在炸弹爆炸前赶到赫敏所在的房间拯救她。 例如，假设地牢可以用以下数字网格表示，网格起始坐标为 $(1,1)$： ``` 2 3 2 2 5 1 5 3 1 3 1 1 ``` 数字 $(i,j)$ 表示哈利在房间 $(i,j)$ 中消灭守卫所需的时间。现在假设赫敏在位置 $(4,2)$，如果 $T = 10$，那么哈利无法及时到达赫敏。然而，如果 $T = 15$，哈利可以在还剩 4 秒的情况下到达赫敏，具体路线是：从 $(1,1)$ 开始，向右移动到 $(1,2)$ 和 $(1,3)$，然后一直向下走到 $(4,3)$，再移动到 $(4,2)$。这共需 11 秒（注意他还需要消灭赫敏所在房间的守卫）。你可以验证，他无法通过其他任何路径在剩余时间超过 4 秒的情况下到达赫敏。注意：如果哈利恰好在 $T$ 秒时到达赫敏所在房间，结果也是「YES」，剩余时间为 0 秒。

第一行包含测试用例的数量 $K$（$1 \le K \le 20$）。每个测试用例的第一行包含两个整数 $M$ 和 $N$，表示地牢的行数和列数（$1 \le M, N \le 100$）。接下来 $M$ 行，每行有 $N$ 个整数字符（仅为个位数）。第 $i$ 行的第 $j$ 个数为在房间 $(i,j)$ 消灭守卫所需的时间。测试用例的最后一行包含三个整数：$a$、$b$ 和 $T$，其中 $(a,b)$ 是赫敏被关押的房间位置，$T$ 是炸弹爆炸前的剩余时间。

对每个测试用例，如果哈利无法成功拯救赫敏，则输出 `NO`。否则，输出两行：第一行内容为 `YES`，第二行为哈利·波特成功救出赫敏时所剩的最大秒数。 **本翻译由 AI 自动生成**