C - Closed Rooms 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 700 点

問題文

高橋君は建物の中に閉じ込められてしまいました。

この建物は 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 個まで選び、それらを開いた状態にする。それらの部屋は以降自由に出入りできるようになる。

ただし、これらの操作では、全く動かなかったり、閉じられている部屋があっても開かなかったりしてもよいです。

高橋君の目標は建物の外につながっている部屋のいずれかにたどり着くことです。そのために必要な魔法の回数の最小値を求めてください。

ただし、はじめに高橋君がいる部屋は建物の外とはつながっていないことが保証されています。

制約

  • 3 ≦ H ≦ 800
  • 3 ≦ W ≦ 800
  • 1 ≦ K ≦ H×W
  • A_{i,j} は # , . , S のいずれかである。
  • A_{i,j}= S となる (i,j) は一意に存在し、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) に移動することができるので、1 回の魔法で十分です。

入力例 2

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

出力例 2

2

高橋君は最初の魔法では移動することができないですが、部屋 (1,2) を 1 回目の魔法で開けることができます。 そして、次の魔法で部屋 (1,2) に移動することで、2 回の魔法で目標を達成できます。

入力例 3

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

出力例 3

2

Score : 700 points

Problem Statement

Takahashi is locked within a building.

This building consists of H×W rooms, arranged in H rows and W columns. We will denote the room at the i-th row and j-th column as (i,j). The state of this room is represented by a character A_{i,j}. If A_{i,j}= #, the room is locked and cannot be entered; if A_{i,j}= ., the room is not locked and can be freely entered. Takahashi is currently at the room where A_{i,j}= S, which can also be freely entered.

Each room in the 1-st row, 1-st column, H-th row or W-th column, has an exit. Each of the other rooms (i,j) is connected to four rooms: (i-1,j), (i+1,j), (i,j-1) and (i,j+1).

Takahashi will use his magic to get out of the building. In one cast, he can do the following:

  • Move to an adjacent room at most K times, possibly zero. Here, locked rooms cannot be entered.
  • Then, select and unlock at most K locked rooms, possibly zero. Those rooms will remain unlocked from then on.

His objective is to reach a room with an exit. Find the minimum necessary number of casts to do so.

It is guaranteed that Takahashi is initially at a room without an exit.

Constraints

  • 3 ≤ H ≤ 800
  • 3 ≤ W ≤ 800
  • 1 ≤ K ≤ H×W
  • Each A_{i,j} is # , . or S.
  • There uniquely exists (i,j) such that A_{i,j}= S, and it satisfies 2 ≤ i ≤ H-1 and 2 ≤ j ≤ W-1.

Input

Input is given from Standard Input in the following format:

H W K
A_{1,1}A_{1,2}...A_{1,W}
:
A_{H,1}A_{H,2}...A_{H,W}

Output

Print the minimum necessary number of casts.

Sample Input 1

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

Sample Output 1

1

Takahashi can move to room (1,2) in one cast.

Sample Input 2

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

Sample Output 2

2

Takahashi cannot move in the first cast, but can unlock room (1,2). Then, he can move to room (1,2) in the next cast, achieving the objective in two casts.

Sample Input 3

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

Sample Output 3

2