AT_agc014_c [AGC014C] Closed Rooms

高桥君被困在一栋建筑物里。 这栋建筑物由 $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}$

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

### 限制条件 - $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 翻译