← 返回题目列表

AtCoder · qupc2018_c

C. 伊东校区

中文机器翻译题面 查看原题

配点 : 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

终点并不一定是安全的格子。