#P3638. [APIO2013] 机器人

[APIO2013] 机器人

题目描述

VRI(Voltron 机器人学会)的工程师建造了 n 个机器人。任意两个兼容的机 器人站在同一个格子时可以合并为一个复合机器人。

我们把机器人用 1 至 n 编号(n ≤ 9)。如果两个机器人的编号是连续的,那 么它们是兼容的,可以合并成一个复合机器人。最初这 n 个机器人各自都只有唯 一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号, 分别是构成它的所有机器人中最小和最大的编号。

例如,2 号机器人只可以与 1 号或 3 号机器人合并。若 2 号机器人与 3 号机 器人合并,可构成编号为 2-3 的复合机器人。如果编号为 2-3 的复合机器人与编 号为 4-6 的复合机器人合并,可构成编号为 2-6 的复合机器人。当所有机器人合 并以后则构成 1-n 复合机器人。

工程师把这 n 个机器人放在了一个封闭的房间中,房间四周均是墙。该房间 被划分成 w × h 个方格。有些方格有障碍物,机器人不可经过或停留;其余方格 允许多个机器人停留,同时允许机器人经过。任何时候一个机器人只占用一个方 格。初始时刻,所有机器人均在不同的方格中。

这些原始的机器人不会自发地移动。它们只有被工程师沿 x 轴或 y 轴推动 后,才会沿推动的方向不断向前直线移动,直至碰到障碍物或墙停止移动。停止 移动后,它会扫描当前的格子是否存在可以与它合并的机器人,如果有,则合并 并继续检查,直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向 上、竖直向下四个方向推动机器人,并且,在机器人尚未停止移动时,不允许推 动其它机器人,因此任何时刻,房间中都只能有一个机器人移动。

为了帮助机器人转向,工程师在一些格子中放置了转向器。具体地说,转向 器分为顺时针转向器(右转器)和逆时针转向器(左转器),顺时针转向器可以 使到达该格子的机器人沿顺时针方向转向 90°;逆时针转向器可以使到达该格 子的机器人沿逆时针方向转向 90°。

现在,我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要 推动机器人多少次,才能把所有的 n 个机器人全部合并(如果可能的话)。

输入格式

你的程序必须从标准输入读入。

输入的第 1 行包含 3 个整数 n、w 和 h,用 空格隔开。

输入文件中接下来的 h 行描述初始时刻房间内的信息,每行包含 w 个字符。 这 w × h 个字符中每一个表示房间中的一个格子,意义如下:

‘1’至‘9’:表示该方格中有一个机器人,编号为这个数字;

‘x’:表示该方格有障碍物;

‘A’:表示该方格中有一个逆时针转向器;

‘C’:表示该方格中有一个顺时针转向器;

‘.’:表示该方格为空地。

输出格式

你的程序必须输出到标准输出。输出仅一个整数,表示最少需要推动的次数。 若不能使所有机器人全部合并,输出-1。

4 10 5 
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
5

提示

第一步:向右推动 3 号机器人,当它碰到转向器后会向上继续移动,直至碰 到墙壁停止移动。

第二步:向上推动 4 号机器人,当它碰到墙壁后停止移动,与 3 号机器人合 并,构成 3-4 号机器人

第三步:向上推动 2 号机器人,当它碰到转向器后会向左移动,由于左侧为 墙壁,故停留在原地。

第四步:向右推动 2 号机器人,由于它在一个转向器上,故它会向上移动, 直至碰到墙壁停止移动,与 1 号机器人合并,构成 1-2 号机器人。

第五步:向左推动 3-4 号机器人,当它碰到墙壁后停止移动,与 1-2 号机器 人合并,构成 1-4 号机器人。

我们将使用以下 4 类输入测例测试你的程序。

  1. (10 分)测例满足 n = 2,w ≤ 10 且 h ≤ 10,没有任何转向器。

  2. (20 分)测例满足 n = 2,w ≤ 10 且 h ≤ 10。

  3. (30 分)测例满足 n ≤ 9,w ≤ 300 且 h ≤ 300。

  4. (40 分)测例满足 n ≤ 9,w ≤ 500 且 h ≤ 500。