问题 4345 --企鹅游戏

4345: 企鹅游戏★★★★★

时间限制: 1 Sec  内存限制: 512 MB
提交: 16  解决: 8
[提交][状态][命题人:]

题目描述

玩家控制两只企鹅分别在两张 20×20 的地图上行动。地图上有一些格子是墙壁,无法到达。当控制企鹅向墙壁或者边界移动时,这个操作会被忽略。

现在同时控制两只企鹅移动,不过企鹅的移动是镜像的:
L :左边的企鹅向左移动,右边的企鹅向右移动;
R :左边的企鹅向右移动,右边的企鹅向左移动;
U :两只企鹅均向上移动;
D :两只企鹅均向下移动;

左边企鹅从 (20,20) 出发前往 (1,20) ,右边企鹅从 (20,1) 出发前往 (1,1) ,求最短操作序列。若有多组解,求字典序最小的解(D<L<R<U)。
注意:当一只企鹅到达目的地而另一只没有到达时,已经到达目的地的企鹅可能仍会离开目的地。

输入

输入由 20 行组成,每行包含 41 个字符,表示网格,中间用空格分隔。
'.' 意味着网格是空的。
'#' 表示网格被阻塞。

输出

输出 22 行。
第一行包含赢得游戏的最少步数。
第二行包含一个由 'L'、'R'、'U'、'D' 组成的字符串,表示获胜的方案。
赢的方案可能有很多,输出字典序最小的那个。
然后输出20行,表示两只企鹅的轨迹,用字符'A'标记轨迹,格式与输入类似。
样例输入
Copy
#................... .............##...#.
.................... .......#.....#.....#
.........#...#.#.... ...#....#...........
#........#.......... ...#..#.............
........#......#.... ..#.#......#.#.....#
......#.#..#.#....#. .......##.....##...#
....#...........#..# ....................
.##................. ...........#..#...#.
.....#.#........#.#. #.........#.#.......
.................... ..#....#..........#.
....#.#..........#.. .#.........#..#..#..
.........#.......#.. ..#.................
...#..#......#...#.. ......#.............
...........#...#.... ....................
..##..#.#....#..#... ..............#...#.
.#..#...#.#.....##.. .........#.#...#....
.#.........#........ ..............#.#...
..##.#........#...#. ##..................
....##.#............ .......#.....#......
..........##........ .#..#.#...........#.
样例输出
Copy
27
LULLUURRUUUUUUULUUUUURRUUUU
#..................A A............##...#.
...................A A......#.....#.....#
.........#...#.#...A A..#....#...........
#........#.........A A..#..#.............
........#......#.AAA AA#.#......#.#.....#
......#.#..#.#...A#. .A.....##.....##...#
....#...........#A.# .A..................
.##..............A.. .A.........#..#...#.
.....#.#........#A#. #A........#.#.......
.................AA. AA#....#..........#.
....#.#..........#A. A#.........#..#..#..
.........#.......#A. A.#.................
...#..#......#...#A. A.....#.............
...........#...#..A. A...................
..##..#.#....#..#.A. A.............#...#.
.#..#...#.#.....##A. A........#.#...#....
.#.........#....AAA. AAA...........#.#...
..##.#........#.A.#. ##A.................
....##.#........AAA. AAA....#.....#......
..........##......AA A#..#.#...........#.

提示

来源

[提交][状态]