题目描述

译自 ROI 2013 Day1 T3. Графический редактор <<Хамелеон>>

一位年轻的计算机科学爱好者正在学习一款新的图形编辑器「变色龙」。这款编辑器非常简洁，仅支持黑白两种颜色，并提供一个工具——「变色龙」。

编辑器的画布是一个 $N \times N$ 的方格网格。画布上有一个光标（即变色龙），可以沿四个方向（上、下、左、右）在网格内移动，每次移动一格。光标的颜色必须始终与所在格子的颜色一致。为此，当光标移动到不同颜色的格子时，必须发生以下两种情况之一：要么光标改变颜色以匹配目标格子的颜色，要么目标格子改变颜色以匹配光标的颜色。例如，如果光标从黑色格子移动到白色格子，它要么变成白色，要么将白色格子变成黑色。如果光标和目标格子的颜色相同，则颜色不发生变化。

初始时，光标的颜色为黑色，位于画布左上角的格子，该格子也为黑色。其余所有格子均为白色。

你需要编写一个程序，确定光标「变色龙」的一系列操作，使得画布最终呈现出输入数据中指定的图案。

输入格式

输入文件的第一行包含一个整数 $N$ $(5 \leq N \leq 100)$，表示画布的大小。

接下来的 $N$ 行描述了需要实现的图案。每行包含 $N$ 个字符，其中 W 表示白色格子，B 表示黑色格子。

最后一行包含一个整数，表示测试点编号。

输出格式

输出文件应包含一行，描述所需的操作序列。

操作符号的定义如下：

• 表示向左、向上、向右或向下移动并改变光标颜色的操作，分别使用小写字母 l、u、r 或 d。
• 表示向左、向上、向右或向下移动并改变格子颜色的操作，分别使用大写字母 L、U、R 或 D。
• 如果光标移动到与其颜色相同的格子，可以使用大写或小写字母。

5
BWWWW
BWWWW
BWBWW
WWWWW
WWWWW
0

DDRRdlU

数据范围与提示

本题的测试数据对选手开放，位于「文件」中。测试点编号与文件名相对应，范围为 $0$ 到 $20$。样例测试点编号为 $0$，用于初步检查。编号从 $1$ 到 $20$ 的测试点用于最终评测。

本题最终评测基于 $20$ 个测试点，每个测试点独立评分，满分 $5$ 分，总分 $100$ 分。测试点通过的条件是输出的操作序列长度不超过 $5000000$ 且能正确实现目标图案。

评分规则如下：

• 前 $10$ 个测试点：通过则获得 $5$ 分。
• 后 $10$ 个测试点：通过则根据操作序列长度评分：
  • 不超过 $3N^{2}$ 个操作：$5$ 分；
  • 不超过 $5N^{2}$ 个操作：$4$ 分；
  • 不超过 $10N^{2}$ 个操作：$3$ 分；
  • 不超过 $2.5N^{3}$ 个操作：$2$ 分；
  • 不超过 $5000000$ 个操作：$1$ 分。

参赛者可使用可视化工具查看操作序列，启动文件位于「文件」的中 visualize.cmd。启动时如不提供参数，将提示选择输入和输出文件。也可以通过命令行参数指定输入和输出文件，命令格式为 visualize.cmd <输入文件> <输出文件>。