← 返回题目列表

Codeforces · 359/E

E. 整洁

中文机器翻译题面 查看原题

西蒙喜欢整洁。所以在睡觉之前,西蒙想完成家里的所有家务。

西蒙的房子从上面看就像一张由 n 行和 n 列组成的长方形桌子。表的所​​有行从上到下编号为 1 到 n。表中的所有列从左到右编号为 1 到 n。表的每个单元格都是一个房间。 (x, y) 对表示房间,位于第 x 行和第 y 列的交叉点。对于每个房间,我们知道灯是否亮着。

最初 Simon 位于房间 (x0, y0)。他想关掉房子里所有房间的灯,然后回到房间(x0,y0)。假设此时西蒙在房间 (x, y) 中。为了达到预期的结果,他可以执行以下步骤:

1. 动作的格式为“1”。该动作是打开房间 (x, y) 中的灯。如果房间已经开着灯,西蒙就无法做到这一点。
2. 动作的格式为“2”。该动作是关闭房间 (x, y) 中的灯。如果房间的灯已经关了,西蒙就无法做到这一点。
3. 操作的格式为“dir”(dir 是一个字符)。动作是移动到 dir 方向的一侧相邻的房间。方向可以是左、右、上、下(对应的方向是L、R、U、D)。此外,西蒙只有在看到 dir 方向有光时才能移动。更正式地说,如果我们代表西蒙想要去的房间,作为(nx, ny),应该有一个整数k(k > 0),那个房间(x + (nx - x)k, y + (ny - y)k)有灯。当然,西蒙不能搬出他的房子。

帮助西蒙,找到让他达到预期结果的行动顺序。

输入

第一行包含三个正整数 n, x0, y0 (2 ≤ n ≤ 500, 1 ≤ x0, y0 ≤ n)。

接下来的 n 行包含房屋中房间的描述。第 i 行包含 n 个空格分隔的整数 ai1, ai2, ..., ain。如果数字 aij 等于 0,则房间 (i, j) 的灯关闭,如果数字 aij 等于 1,则房间 (i, j) 的灯打开。保证至少一个房间有灯。

输出

如果没有所需的操作序列,则打印“NO”(不带引号)。否则,以字符串形式打印“YES”(不带引号)和所需操作序列的描述。请注意,您不必最小化操作序列的长度,但不应使用超过 3·106 个操作。

示例

输入 #1

3 1 1
1 0 0
0 1 0
1 0 0

输出 #1

YES
D1R2L2D2UU2

输入 #2

3 1 1
1 0 0
0 1 0
0 0 1

输出 #2

NO