← 返回题目列表

AtCoder · codefestival_2016_final_j

J. 新游戏

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

分数: 2100 点

问题陈述

Snuke 有一块板,上面有 N \times N 网格,以及 N \times N 瓷砖。

作为网格周边一部分的正方形的每条边都连接有一个插座。 也就是说,网格的每一面都附有 N 套接字,总计 4 \times N 插座。 这些插座标记如下:

  • 网格顶部的插座: U1, U2, ..., UN 从左到右
  • 网格底部的插座: D1, D2, ..., DN 从左到右
  • 网格左侧的插座: L1, L2, ..., LN 从上到下
  • 网格右侧的插座: R1, R2, ..., RN 从上到下
图:插座的标签

Snuke 可以将每个插槽中的方块插入到插槽所连接的方块中。 当该方格已被棋子占据时,占据的棋子将被推入下一个方格,而当下一个方格也被另一方格占据时,另一占据的方格也将被推入,依此类推。 Snuke 无法插入图块,因为这会导致图块被推出网格。 插入图块时图块的行为在示例输入/输出中详细演示 1.

Snuke 正在尝试插入 N \times N 从插槽中一张一张地贴出瓷砖,达到每格都有一块瓷砖的状态。 在这里,他必须准确插入 U_i 插座上的瓷砖 Ui, D_i 插座上的瓷砖 Di, L_i 插座上的瓷砖 Li 和 R_i 插座上的瓷砖 Ri。 确定是否可以在限制下插入图块。如果可以的话,瓷砖应以什么顺序从插座插入?

约束

  • 1≦N≦300
  • U_i,D_i,L_i 和 R_i 是非负整数。
  • 所有值的总和 U_i,D_i,L_i 和 R_i 等于 N \times N.

部分分数

  • 2000 通过满足以下条件的测试集将获得积分 N≦40.
  • 附加 在没有额外限制的情况下通过测试集将获得 100 分数。

输入

输入由标准输入按以下格式给出:

N
U_1 U_2 ... U_N
D_1 D_2 ... D_N
L_1 L_2 ... L_N
R_1 R_2 ... R_N

输出

如果可以插入图块,以便每个方格都包含一个图块,请按照图块插入的顺序打印插槽的标签,每行一个。如果不可能,则打印 NO 代替。如果存在多个解决方案,请打印其中任何一个。


示例输入 1

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

示例输出 1

L1
L1
L1
L3
D1
R2
U3
R3
D2

Snuke可以插入方块,如下图所示。箭头表示从哪里插入图块,圆圈表示图块,圆圈中写的数字表示在该图块之前插入了多少个图块。


示例输入 2

2
2 0
2 0
0 0
0 0

示例输出 2

NO