2013亚太地区信息学奥林匹克竞赛APIO2013中文试题

2013 亚太地区信息学奥林匹克竞赛 APIO 2013 竞赛时间：2013 年 5 月 11 日 9:00-14:00 题目名称 机器人 道路费用 出题人 英文名称 ROBOTS TOLL TASKSAUTHOR 输入 标准输入 输出 标准输出 每个测试点时限 1.5 秒 2.5 秒 / 内存限制 128 MB 128MB / 试题总分 100 100 100 测试点数目 20 20 8 每个测试点分值 5 5 见题面 编译器版本及编译选项见考试注意事项。 2013 亚太地区信息学奥林匹克竞赛 机器人 机器人 【问题描述】 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’：表示该方格中有一个顺时针转向器； ‘.’：表示该方格为空地。 第 2 页 共 11 页 2013 亚太地区信息学奥林匹克竞赛 机器人 【输出格式】 你的程序必须输出到标准输出。输出仅一个整数，表示最少需要推动的次数。 若不能使所有机器人全部合并，输出-1。 【样例输入】 4 10 5 1......... AA...x4... ..A..x.... 2....x.... ..C.3.A... 【样例输出】 5 【样例说明】 第一步：向右推动 3 号机器人，当它碰到转向器后会向上继续移动，直至碰 到墙壁停止移动。 第二步：向上推动 4 号机器人，当它碰到墙壁后停止移动，与 3 号机器人合 并，构成 3-4 号机器人 第三步：向上推动 2 号机器人，当它碰到转向器后会向左移动，由于左侧为 墙壁，故停留 ... ...