#P3633. 超级翻转

    ID: 2828 传统题 2000ms 256MiB 尝试: 6 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-线性代数与代数GF(2) 消元增广矩阵构造与建模奇偶性分析不变量分析图构造图论Hierholzer 算法CF2500

超级翻转

超级翻转

题目描述

在一个 n×nn\times n 的网格中,每个小方格内放有一块可以翻面的方块,方块一面为黑色,另一面为白色。初始时,每个方块朝上的颜色已知。

另有一个可以沿网格线移动的“动子”,初始停在网格的某个顶点上。图一给出了一个 4×44\times4 网格的初始状态,图中黄色圆点表示动子的位置。

图一,动子的初始位置和各方格的初始颜色

图一:4×4 网格的初始状态

动子每次沿一条网格边移动,从当前顶点到达相邻顶点。每经过一条网格边,所有与这条边相邻的小方格都会翻面一次,即黑色变为白色、白色变为黑色。

  • 经过网格内部的边时,边两侧的两个方块都翻面;
  • 经过网格边界上的边时,只有与它相邻的一个方块翻面。

例如,从图一中的位置出发:

图二,向右移动一步后翻转两个方格

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

图三,沿左侧边界向下移动一步后翻转一个方格

图三:动子向下移动一步后,经过的边旁边的一个方块翻面。 动子可以重复经过同一条边,也可以经过同一个顶点多次。

给定各小方格的初始颜色及动子的初始顶点,请构造一条合法的移动路径,使得所有小方格最终都变为白色。动子最终停留在哪个顶点没有限制。

如果不存在这样的路径,输出 No Solution!。

输入格式

第一行一个整数 TT,表示测试用例个数。

每组测试数据的格式为:

  1. 一行一个整数 nn,表示网格有 nn 行、nn 列小方格。
  2. 接下来 nn 行,每行 nn 个整数,描述各小方格的初始颜色:0 表示白色,1 表示黑色。
  3. 最后一行两个整数 x,yx,y,表示动子的初始位置。网格顶点以左上角为 (1,1)(1,1),向下行坐标增加,向右列坐标增加,因此左下角顶点是 (n+1,1)(n+1,1)。

输出格式

对于每组测试数据,在单独的一行输出一个答案:

  • 若无解,输出 No Solution!(注意大小写及空格)。
  • 否则输出由 L、R、U、D 组成的字符串,依次表示向左、向右、向上、向下移动一条网格边。

输出的路径必须始终在网格顶点之间移动,且最后所有方格均为白色;移动次数不超过 50005000。若存在多种合法路径,输出任意一种即可。若初始已经全部为白色,长度为 00 的路径也合法(即输出一个空行)。

样例输入

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 四次移动;沿途按照规则翻转相邻方格,最终全部变为白色。

第三组无解。

数据范围

数据比例 限制
40%40\% n≤5n\le 5
100%100\% 1≤T≤51\le T\le 5,1≤n≤151\le n\le 15

每个小方格的颜色为 00 或 11,起点坐标满足 1≤x,y≤n+11\le x,y\le n+1。