分数: 700 点
问题陈述
高桥被锁在建筑物内。
该建筑包括 H×W 房间,安排在 H 行和 W 列。
我们将表示房间位于 i第行和 j第列为 (i,j)。这个房间的状态用一个字符来表示 A_{i,j}。如果 A_{i,j}= #,房间被锁,无法进入;如果 A_{i,j}= .,房间没有上锁,可以自由进入。
高桥现在在的房间里 A_{i,j}= S,也可以自由输入。
每个房间 1-st 行, 1-st 列, H第行或 W第列,有一个出口。 其他每个房间 (i,j) 连接到四个房间: (i-1,j), (i+1,j), (i,j-1) 和 (i,j+1).
高桥将使用他的魔法离开建筑物。在一次演员中,他可以执行以下操作:
- 最多移动到相邻的房间 K 次,可能为零。在这里,上锁的房间无法进入。
- 然后,最多选择并解锁 K 上锁的房间,可能为零。从那时起,这些房间将保持解锁状态。
他的目标是到达一个有出口的房间。找到执行此操作所需的最小强制转换次数。
保证高桥最初位于一个没有出口的房间。
约束
- 3 ≤ H ≤ 800
- 3 ≤ W ≤ 800
- 1 ≤ K ≤ H×W
- 每个 A_{i,j} is
#,.orS. - 唯一存在 (i,j) 这样 A_{i,j}=
S,并且满足 2 ≤ i ≤ H-1 和 2 ≤ j ≤ W-1.
输入
输入由标准输入按以下格式给出:
H W K
A_{1,1}A_{1,2}...A_{1,W}
:
A_{H,1}A_{H,2}...A_{H,W}
输出
打印所需的最少铸造次数。
示例输入 1
3 3 3 #.# #S. ###
示例输出 1
1
高桥可以移动到房间 (1,2) 一劳永逸。
示例输入 2
3 3 3 ### #S# ###
示例输出 2
2
高桥在第一次施法中无法移动,但可以解锁房间 (1,2)。 然后,他就可以移动到房间 (1,2) 在下一次施法中,通过两次施法实现目标。
示例输入 3
7 7 2 ####### ####### ##...## ###S### ##.#.## ###.### #######
示例输出 3
2