题目描述

高桥君被困在一栋建筑物里。

这栋建筑物由 $H$ 行 $W$ 列共 $H×W$ 个房间组成，自上而下第 $i$ 行，自左而右第 $j$ 列的房间用 $(i,j)$ 表示，该房间的状态由 $A_{i,j}$ 描述。若 $A_{i,j}=$ #，则该房间为封闭房间；若 $A_{i,j}=$ .，则该房间可以自由进出。$A_{i,j}=$ S 的房间是高桥君当前所在的房间，且该房间同样可以自由进出。

此外，位于第 $1$ 行、第 $1$ 列、第 $H$ 行、第 $W$ 列之一的房间都与建筑物外部相连，除此以外的每个房间 $(i,j)$ 与 $4$ 个相邻房间 $(i-1,j)$、$(i+1,j)$、$(i,j-1)$、$(i,j+1)$ 相邻。

为了逃出这栋建筑物，高桥君打算使用魔法。每次使用魔法可以进行如下操作：

• 高桥君可以从当前房间移动到相邻的房间，最多连续移动 $K$ 次，且不能进入封闭房间。
• 之后，他可以选择至多 $K$ 个封闭房间，并将它们变为打开状态（今后这些房间可以自由进出）。

以上操作中，可以选择不移动或者不打开任何封闭房间。

高桥君的目标是到达与建筑物外部相连的任意房间。请你求出他至少需要施展多少次魔法才能达成目标。

保证初始时高桥君所在的房间与建筑物外部没有直接相连。

输入格式

输入从标准输入中给出，格式如下：

$H$ $W$ $K$

$A_{1,1}A_{1,2}\ldots A_{1,W}$

$\vdots$

$A_{H,1}A_{H,2}\ldots A_{H,W}$

输出格式

输出高桥君所需施展魔法的最小次数。

样例 1

输入

3 3 3
#.#
#S.
###

输出

1

样例 2

输入

3 3 3
###
#S#
###

输出

2

样例 3

输入

7 7 2
#######
#######
##...##
###S###
##.#.##
###.###
#######

输出

2

说明/提示

限制条件

• $3\leq H\leq 800$
• $3\leq W\leq 800$
• $1\leq K\leq H×W$
• $A_{i,j}$ 仅可能为 #、.、S 中的一个。
• 恰好存在唯一的 $A_{i,j}=S$，且 $2\leq i\leq H-1,\ 2\leq j\leq W-1$。

样例解释 1

高桥君可以在第一次魔法中直接移动到房间 $(1,2)$，所以只需施展 $1$ 次魔法。

样例解释 2

高桥君在第一次魔法无法移动，但可以在第一次魔法中打开房间 $(1,2)$，然后在下一次魔法中移动到 $(1,2)$，共需施展 $2$ 次魔法即可达成目标。

由 ChatGPT 5 翻译