AT_abc301_e [ABC301E] Pac-Takahashi

[problemUrl]: https://atcoder.jp/contests/abc301/tasks/abc301_e $ H $ 行 $ W $ 列のグリッドがあります。 上から $ i $ 行目、左から $ j $ 列目のマス目を $ (i,j) $ と表します。 グリッドの各マスはスタートマス、ゴールマス、空マス、壁マス、お菓子マスのいずれかです。 $ (i,j) $ が何のマスであるかは文字 $ A_{i,j} $ によって表され、$ A_{i,j}= $ `S` のときスタートマス、 $ A_{i,j}= $ `G` のときゴールマス、 $ A_{i,j}= $ `.` のとき空マス、 $ A_{i,j}= $ `#` のとき壁マス、 $ A_{i,j}= $ `o` のときお菓子マスです。 ここで、スタートマスとゴールマスはちょうど $ 1 $ つずつあり、お菓子マスは **$ 18 $ 個以下**であることが保証されます。 高橋くんは現在スタートマスにいます。 高橋くんは、上下左右に隣接するマスであって壁マスでないマスに移動することを繰り返し行えます。 高橋くんは今から $ T $ 回以下の移動によってゴールマスに到達したいです。 そのようなことは可能かどうか判定してください。 可能な場合は、最終的にゴールマスにいるという条件のもとで、移動の途中に訪れるお菓子マスの数の最大値を求めてください。 ただし、$ 1 $ つのお菓子マスに複数回訪れた場合でも、カウントするのは $ 1 $ 回のみです。

N/A

N/A

### 制約 - $ 1\leq\ H,W\ \leq\ 300 $ - $ 1\ \leq\ T\ \leq\ 2\times\ 10^6 $ - $ H,W,T $ は整数 - $ A_{i,j} $ は `S`, `G`, `.`, `#`, `o` のいずれか - $ A_{i,j}= $ `S` を満たす $ (i,j) $ の組がちょうど $ 1 $ つ存在する - $ A_{i,j}= $ `G` を満たす $ (i,j) $ の組がちょうど $ 1 $ つ存在する - $ A_{i,j}= $ `o` を満たす $ (i,j) $ の組は **$ 18 $ 個以下** ### Sample Explanation 1 $ (1,1)\ \rightarrow\ (1,2)\ \rightarrow\ (1,3)\ \rightarrow\ (2,3)\ \rightarrow\ (1,3) $ と $ 4 $ 回移動すると、 $ 1 $ 個のお菓子マスを訪れた上で最終的にゴールマスにいることができます。 $ 5 $ 回以下の移動で $ 2 $ 個のお菓子マスを訪れた上で最終的にゴールマスにいることはできないので、$ 1 $ が答えです。 なお、$ (1,1)\ \rightarrow\ (2,1)\ \rightarrow\ (1,1)\ \rightarrow\ (1,2)\ \rightarrow\ (1,3)\ \rightarrow\ (2,3) $ と移動すると $ 5 $ 回の移動で $ 2 $ 個のお菓子マスを訪れることができますが、最終的にゴールマスにいないため無効であることに注意してください。 ### Sample Explanation 2 $ 1 $ 回以下の移動でゴールマスに到達することはできません。