配点 : 400 点
問題文
牛君和野猪被困在迷宫里了。
迷宫是 H 行 W 以列的格子表示。从上到下 i 行,从左到右 j 用在列中的格子来表示 (i,j) 用...表示格子 (i,j) 的信息是 s_{ij} 被给予。
- s_{ij} 是
时间保证在
S的时候,格子 (i,j) 是起点格子,牛君最初就在这个格子上。 - s_{ij} 是
时间保证在
G的时候,格子 (i,j) 是终点格子。 - s_{ij} 是
时间保证在
#的时候,格子 (i,j) 是墙壁格子,不能通过这个格子。 - s_{ij} 是
时间保证在
@的时候,格子 (i,j) 上有野猪。 - s_{ij} 是
时间保证在
.的时候,格子 (i,j) 是空格子。
牛君可以移动到墙壁格子外侧上下左右相邻的格子。
将“安全格子”定义为,从该格子出发,通过不超过 X 次移动可以到达的所有格子上都没有野猪的格子。
求牛君从起点格子仅通过安全格子到达终点格子的最少移动次数。
制約
- 4 \leq H, W \leq 10^3
- 0 \leq X \leq 10^6
- s_{ij} 是
给出了
S或 给出G或 给出#或 给出.或 给出@组成的 - 起点和终点各自 1 存在一个
- 野猪所在的格子是 1 存在多个
- 起点是安全的格子,这一点是保证的
- 迷宫的期望 1 格子被墙围住
- H,W,X 是一个整数
部分点
- H, W \leq 50 在满足...的数据集的情况下正确回答时,30 点。
入力
输入是按以下格式从标准输入给出的。
H W X
s_{11}...s_{1W}
:
s_{H1}...s_{HW}
出力
请输出从起点到终点的最小移动次数。但是,如果无论如何移动都无法从起点移动到终点, -1 请输出。
入力例 1
6 5 1 ##### #S.@# #...# #...# #@.G# #####
出力例 1
5
(2,2) → (3,2) → (3,3) → (4,3) → (4,4) → (5,4) 通过移动,只通过安全的格子从起点到终点 5 可以在...次移动中到达。
入力例 2
5 6 0 ###### #S...# #@@@.# #G...# ######
出力例 2
8
入力例 3
5 5 1 ##### #S..# #...# #.@G# #####
出力例 3
-1
终点并不一定是安全的格子。