配点: 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} 是
#。 - 通过问题陈述中所示的动作,可以将所有行李放置在目的地广场上。
採点
入力
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 操作来清理。
- 向下移动。
- 向右移动。
- 将行李推到右侧的同时移动。
- 一边移动一边向下推行李。
- 向上移动。
- 向上移动。
- 向右移动。
- 向右移动。
- 向下移动。
- 将行李推向左侧的同时移动。
此输入示例还单击此处考虑一块分为你可以用手玩。