C - Sokoban 解説 /

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

配点： 100 点

クリスマス，そして年の瀬ということで，うさぎは部屋の片づけをしようと思い立った．今年は，荷物を投げて動かしたりはしない．

問題文

うさぎの部屋は H \times W の長方形のマス目状になっている．部屋の各マスは，「通常のマス」「片づけ先のマス」「固定家具のマス」の 3 種類のいずれかである．最初，うさぎと何個かの荷物が，固定家具でない相異なるマスに位置している．上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスの情報は文字 A_{i,j} で表され，以下を意味する．

  • .：通常のマス
  • R：通常のマスであり，うさぎがいる
  • a：通常のマスであり，荷物がある
  • O：片付け先のマス
  • @：片付け先のマスであり，荷物がある
  • #：固定家具のマス

うさぎは，以下のいずれかの行動を何回か，何らかの順番で行い，すべての荷物が片づけ先のマスに配置されている状態にしたい．

  • 今いるマスと上下左右に隣接している空きマスに移動する．
  • 今いるマスと上下左右に隣接しているマスにある荷物を，移動方向に 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 点が与えられる．
  • 入力ファイルはこちらからダウンロードできる．
  • 実際の入力ファイルに対して部屋の片づけをこちら (または zip 同梱の html) で手で遊べる．

入力

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 行に出力せよ．

入力例 1

6 7
#######
#R....#
#..@..#
###a###
###O###
#######

出力例 1

10

例えば，以下の 10 回の操作で片づけることができる．

  1. 下に移動する．
  2. 右に移動する．
  3. 右に荷物を押しながら移動する．
  4. 下に荷物を押しながら移動する．
  5. 上に移動する．
  6. 上に移動する．
  7. 右に移動する．
  8. 右に移動する．
  9. 下に移動する．
  10. 左に荷物を押しながら移動する．

この入力例も，こちらで手で遊べる．