AT_qupc2018_c Ito Campus

[problemUrl]: https://atcoder.jp/contests/qupc2018/tasks/qupc2018_c うしくん と イノシシ が迷路に閉じ込められてしまいました。 迷路は $ 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 $ 回以下の移動で行くことのできる全てのマスにイノシシがいないようなマスと定義します。 うしくん がスタート地点から安全なマスのみを通ってゴール地点に到達するまでの最小の移動回数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ X $ $ s_{11}...s_{1W} $ $ : $ $ s_{H1}...s_{HW} $

スタート地点からゴール地点までの最小の移動回数を出力してください。ただし、どのように移動してもスタート地点からゴール地点に移動できない場合は `-1` を出力してください。

### 制約 - $ 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 $ 点が与えられる。 ### Sample Explanation 1 $ (2,2) $ → $ (3,2) $ → $ (3,3) $ → $ (4,3) $ → $ (4,4) $ → $ (5,4) $ と移動することで、スタートから安全なマスのみを通ってゴールまで $ 5 $ 回で移動できます。 ### Sample Explanation 3 ゴールが安全なマスとは限りません。