#P3633. 超级翻转
超级翻转
超级翻转
题目描述
在一个 的网格中,每个小方格内放有一块可以翻面的方块,方块一面为黑色,另一面为白色。初始时,每个方块朝上的颜色已知。
另有一个可以沿网格线移动的“动子”,初始停在网格的某个顶点上。图一给出了一个 网格的初始状态,图中黄色圆点表示动子的位置。

图一:4×4 网格的初始状态
动子每次沿一条网格边移动,从当前顶点到达相邻顶点。每经过一条网格边,所有与这条边相邻的小方格都会翻面一次,即黑色变为白色、白色变为黑色。
- 经过网格内部的边时,边两侧的两个方块都翻面;
- 经过网格边界上的边时,只有与它相邻的一个方块翻面。
例如,从图一中的位置出发:

图二:动子向右移动一步后,经过的边两侧的两个方块翻面。

图三:动子向下移动一步后,经过的边旁边的一个方块翻面。 动子可以重复经过同一条边,也可以经过同一个顶点多次。
给定各小方格的初始颜色及动子的初始顶点,请构造一条合法的移动路径,使得所有小方格最终都变为白色。动子最终停留在哪个顶点没有限制。
如果不存在这样的路径,输出 No Solution!。
输入格式
第一行一个整数 ,表示测试用例个数。
每组测试数据的格式为:
- 一行一个整数 ,表示网格有 行、 列小方格。
- 接下来 行,每行 个整数,描述各小方格的初始颜色:
0表示白色,1表示黑色。 - 最后一行两个整数 ,表示动子的初始位置。网格顶点以左上角为 ,向下行坐标增加,向右列坐标增加,因此左下角顶点是 。
输出格式
对于每组测试数据,在单独的一行输出一个答案:
- 若无解,输出
No Solution!(注意大小写及空格)。 - 否则输出由
L、R、U、D组成的字符串,依次表示向左、向右、向上、向下移动一条网格边。
输出的路径必须始终在网格顶点之间移动,且最后所有方格均为白色;移动次数不超过 。若存在多种合法路径,输出任意一种即可。若初始已经全部为白色,长度为 的路径也合法(即输出一个空行)。
样例输入
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!
样例说明
第一组中,动子从左上角向右移动一条网格边,唯一的小方格被翻转一次,从黑色变为白色。
第二组中,动子依次进行 U、L、D、R 四次移动;沿途按照规则翻转相邻方格,最终全部变为白色。
第三组无解。
数据范围
| 数据比例 | 限制 |
|---|---|
| , |
每个小方格的颜色为 或 ,起点坐标满足 。