← 返回题目列表

AtCoder · xmascon19_c

C. 推箱子

中文机器翻译题面 查看原题

配点: 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. 将行李推向左侧的同时移动。

此输入示例还单击此处考虑一块分为你可以用手玩。