← 返回题目列表

AtCoder · agc014_c

C. 封闭的房间

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

分数: 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 # , . or S.
  • 唯一存在 (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