pudding

問題文

あなたは次のようなゲームを遊んでいます。 このゲームについて、クリアにかかるターン数の最小値を出力してください。ただし、有限ターンでクリアできない場合は -1 を出力してください。

盤面

• 盤面は $H$ 行 $W$ 列のグリッドで、上から $i$ 行目・左から $j$ 列目のマスを $(i,j)$ と表す。各マスの状態を $S_{i,j}$ とする（$1 \le i \le H,\ 1 \le j \le W$）。
• 各マスは次のいずれかである。
  • 空マス：通過可能。$S_{i,j}=$ .
  • 壁マス：通過不可。$S_{i,j}=$ #
  • プリンマス：通過可能。$S_{i,j}=$ P

行動

• キャラクター Puppuka-san は、はじめに $(1, 1)$ からスタートします。
• あなたはキャラクター Puppuka-san を操作する。各ターン、次の 8 行動のうちちょうど 1 つを選ぶ（上／下／左／右の 4 方向 ×2 種）。
  • 移動（上／下／左／右）
    • 現在位置が $(i,j)$ のとき、選んだ方向の隣接マスへ移動する（上なら $(i-1,j)$、下なら $(i+1,j)$、左なら $(i,j-1)$、右なら $(i,j+1)$）。
    • 盤外や壁マスには移動できない。
    • 移動先がプリンマスなら、移動後にそのプリンを食べる。そのマスは空マスとなる。
  • ブレス（上／下／左／右）
    • 選んだ方向に息を吹きかける。Puppuka-san は肺活量が非常に大きいため、選んだ方向に対して距離 $K$ 以内のマスに存在する壁・プリンは消滅する。
    • より厳密には、現在位置が $(i,j)$ のとき、選んだ方向に距離 $t=1,2,\dots,K$ の各位置（上なら $(i-t,j)$、下なら $(i+t,j)$、左なら $(i,j-t)$、右なら $(i,j+t)$）の全てのマスを空マスに変える（盤外は無視する）。
    • プリンマスを 1 つでも空マスに変えてしまった時点で失敗となる。
    • この行動では Puppuka-san は移動しない。
    • 空マスは空マスのまま変化しない。

目的

• 初期状態で盤面に存在するすべてのプリンを食べ切ればクリアとする。

制約

• $1 \leq H \leq 1000$
• $1 \leq W \leq 1000$
• $2 \leq HW \leq 1000$
• $1 \leq K \leq 1000$
• $H,W,K$ は整数
• $(1,1)$ は空マス。 ($S_{1, 1}=$.)
• $S_{i,j} \, (1 \leq i \leq H, 1 \leq j \leq W)$ は [., #, P] のいずれか。
• プリンマスが 盤面内に $1$ 個以上存在することが保証される。
• 盤面に存在する壁マスの数、プリンマスの数の和は $10$ 以下。

入力

入力は以下の形式で標準入力から与えられます。

出力

クリアにかかるターン数の最小値を出力してください。ただし、有限ターンでクリアできない場合は -1 を出力してください。

入力例 1

2 3 1
.#P
...

出力例 1

3

以下のように行動することで $3$ ターンでクリアできます。

• $1$ ターン目: 右にブレスします。
• $2$ ターン目: 右に移動します。
• $3$ ターン目: 右に移動します。

入力例 2

3 1 100
.
#
P

出力例 2

-1

どのように操作しても有限ターンでクリアすることはできません。よって -1 を出力します。

入力例 3

4 6 3
..#.#P
.#.#P#
#.....
P..#..

出力例 3

14

盤面に存在する壁マスの数、プリンマスの数の和は $10$ 以下であることに注意してください。

入力例 4

5 1 7
.
P
P
P
P

出力例 4

4

壁マスが存在しないこともあります。