AT_xmascon19_c Sokoban

[problemUrl]: https://atcoder.jp/contests/xmascon19/tasks/xmascon19_c うさぎの部屋は $ H\ \times\ W $ の長方形のマス目状になっている．部屋の各マスは，「通常のマス」「片づけ先のマス」「固定家具のマス」の $ 3 $ 種類のいずれかである．最初，うさぎと何個かの荷物が，固定家具でない相異なるマスに位置している．上から $ i $ 行目 ($ 1\ \le\ i\ \le\ H $)，左から $ j $ 列目 ($ 1\ \le\ j\ \le\ W $) のマスの情報は文字 $ A_{i,j} $ で表され，以下を意味する． - `.`：通常のマス - `R`：通常のマスであり，うさぎがいる - `a`：通常のマスであり，荷物がある - `O`：片付け先のマス - `@`：片付け先のマスであり，荷物がある - `#`：固定家具のマス うさぎは，以下のいずれかの行動を何回か，何らかの順番で行い，すべての荷物が片づけ先のマスに配置されている状態にしたい． - 今いるマスと上下左右に隣接している空きマスに移動する． - 今いるマスと上下左右に隣接しているマスにある荷物を，移動方向に $ 1 $ つ先の空きマスに押して動かし，動かした荷物があったマスに移動する． ただし，「空きマス」とは，固定家具のマスでなく，荷物もない状態のマスのことである． 必要な行動回数の最小値を求めよ．**なお，この問題では，すべての入力ファイルが公開される (「採点」を参照のこと)．**

> $ H $ $ W $ $ A_{1,1}\ A_{1,2}\ \cdots\ A_{1,W} $ $ A_{2,1}\ A_{2,2}\ \cdots\ A_{2,W} $ $ \vdots $ $ A_{H,1}\ A_{H,2}\ \cdots\ A_{H,W} $

必要な行動回数の最小値を $ 1 $ 行に出力せよ．

### 制約 - $ 5\ \le\ H\ \le\ 400 $． - $ 5\ \le\ W\ \le\ 400 $． - $ A_{i,j} $ は `.`, `R`, `a`, `O`, `@`, `#` のいずれかである ($ 1\ \le\ i\ \le\ H $，$ 1\ \le\ j\ \le\ W $)． - $ A_{i,j} $ のうちちょうど $ 1 $ 個が `R` である． - $ A_{i,j} $ のうち `a` の個数と `O` の個数は等しく，$ 1 $ 個以上である． - $ i\ =\ 1 $ または $ i\ =\ H $ または $ j\ =\ 1 $ または $ j\ =\ W $ のとき，$ A_{i,j} $ は `#` である． - 問題文で示された行動により，すべての荷物が片づけ先のマスに配置されている状態にすることが可能である． ### 採点 - テストケースは `01.txt`, `02.txt`, `03.txt`, `04.txt`, `05.txt` の $ 5 $ 個あり，それぞれ正解すると $ 7 $ 点，$ 11 $ 点，$ 17 $ 点，$ 25 $ 点，$ 40 $ 点が与えられる． - **入力ファイルは[こちら](https://img.atcoder.jp/xmascon19/sokoban.zip)からダウンロードできる．** - 実際の入力ファイルに対して部屋の片づけを[こちら](https://img.atcoder.jp/xmascon19/sokoban.html) (または zip 同梱の html) で**手で遊べる．** ### Sample Explanation 1 例えば，以下の $ 10 $ 回の操作で片づけることができる． 1. 下に移動する． 2. 右に移動する． 3. 右に荷物を押しながら移動する． 4. 下に荷物を押しながら移動する． 5. 上に移動する． 6. 上に移動する． 7. 右に移動する． 8. 右に移動する． 9. 下に移動する． 10. 左に荷物を押しながら移動する． この入力例も，\[こちら\](https://img.atcoder.jp/xmascon19/sokoban.html)で\*\*手で遊べる．\*\*