No testdata at current.

https://www.luogu.com.cn/problem/T310723

企鹅走迷宫

题目描述

元元在玩一个两只企鹅走迷宫的复古小游戏。游戏在两个 $20×20$ 大小的棋盘中进行，左右相邻，其中有一些砖块阻挡前进。

企鹅一步只能向上下左右四个方向走一格，如果它的前进方向上有砖块，则会原地不动。玩家可以向四个方向移动这两只企鹅，但这两只企鹅的移动方式是镜像的，具体表现为：

L：左边的企鹅向左走，右边的企鹅向右走。
R：左边的企鹅向右走，右边的企鹅向左走。
U：同时向上移动。
D：同时向下移动。

注：一次操作可以仅让一只企鹅发生移动，另一只企鹅受阻碍而原地不动。

左边的企鹅从 $(20,20)$ 开始，想要移动到 $(1,20)$。右边的企鹅从 $(20,1)$ 开始时，想要移动到 $(1,1)$，当两只企鹅都到达目的地时，游戏结束。

找到赢得游戏的最少操作次数（保证总算是存在一种赢法，且企鹅的初始位置不存在砖块），如果存在多种赢得游戏的最短操作序列，则输出字典序最小的(D$<$L$<$R$<$U)。

注：当一个企鹅到达终点而另一只企鹅没有到达时，到达终点的企鹅仍然可以移动出终点。

输入格式

输入包含 $21$ 行。

第一行一个整数 $x$，为$1$或$2$，表示测试数据的类型。

如果 $x=1$，则只需要输出最小步数。

如果 $x=2$，则需要输出步数和操作序列。

接下来的 $20$ 行，每行有 $41$ 个字符，表示两个 $20×20$ 的棋盘，中间以空格作为分隔。

以 . 表示空地，# 表示砖块。

输出格式

输出包含 $22$ 行。

第一行输出赢得游戏所须的最小步数。

第二行包含所需的操作序列。（如果数据类型 $x=1$ 则无此行）

接下来 $20$ 行输出整个地图，并用 A 代替企鹅，以表示企鹅的行动路线（详见样例）。

样例 #1

样例输入 #1

2
#................... .............##...#.
.................... .......#.....#.....#
.........#...#.#.... ...#....#...........
#........#.......... ...#..#.............
........#......#.... ..#.#......#.#.....#
......#.#..#.#....#. .......##.....##...#
....#...........#..# ....................
.##................. ...........#..#...#.
.....#.#........#.#. #.........#.#.......
.................... ..#....#..........#.
....#.#..........#.. .#.........#..#..#..
.........#.......#.. ..#.................
...#..#......#...#.. ......#.............
...........#...#.... ....................
..##..#.#....#..#... ..............#...#.
.#..#...#.#.....##.. .........#.#...#....
.#.........#........ ..............#.#...
..##.#........#...#. ##..................
....##.#............ .......#.....#......
..........##........ .#..#.#...........#.

样例输出 #1

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#..#.#...........#.

提示

数据范围

对于 $30\%$ 的数据，$x=1$。

对于另外 $10\%$ 的数据，地图中没有障碍。

对于另外 $10\%$ 的数据，只存在一条合法路径。

对于剩余 $50\%$ 的数据，$x=2$ 且没有额外限制。