超级翻转

时间限制:10s      空间限制:128MB

题目描述

图一


有一个n*n的网格,每一“格”上有一个可以翻转的方块,方块的两面分别涂成黑、白两种颜色。另外,有一个沿着网格线活动的东西——不妨称之为“动子”。初始时,每个方块随机地被翻成黑或白色,“动子”停在网格线的某个顶点上。例如如图一就是一个4*4的网格的一种可能的开局情况。

“动子”在网格线上运动时,从一个顶点A到相邻的另一个顶点B之后,以网格线AB为边的两个或一个网格上的方块就会翻转——白变黑,黑变白。例如图一的“动子”向右移动一步之后变成图二,向下移动一步之后变成图三。

图三

图二



给定一个初始状态,求“动子”的一种运动轨迹,可以将所有的格子变成白色,最后“动子”停在哪里是无所谓的。


输入格式

第一行T表示数据组数

对于每组数据,第一行n表示网格大小

接下来nn列描述初始网格,0表示白色,1表示黑色

接下来一行x y表示动子的初始位置,左上角为(1,1),左下角为(n+1,1)


输出格式

   对于每组数据,在一行中输出一个相应的答案

    若无解则输出“No Solution!”,否则输出一个仅包含‘L’R’U’‘D’(上下左右)的字符串表示“动子”的移动路线,有多解时任意输出任意一组解即可,要求输出的解长度不超过5000


样例输入

3
1
1
1 1
2
0 1
1 0
2 2
7
1 1 0 0 1 0 1 
1 1 0 1 0 1 1 
1 0 1 0 1 1 1 
0 1 0 1 1 0 1 
1 1 1 1 1 1 1 
1 1 1 1 1 1 1 
1 1 1 1 1 1 1 
1 1

样例输出

R
ULDR
No Solution!

提示

T≤5,1≤n≤15

请不要提交,期待SPJ


题目来源

没有写明来源

Menuappsclose