33OJ
登录 注册

#P3969. [TJOI2014] 拼图

[TJOI2014] 拼图

题目描述

小 Z 最近迷上了拼图游戏,然而智商有限,他总是无法拼出完整图案。游戏是这样的:首先小 Z 会得到一些拼图碎片,然后他试着重新排列这些碎片使得它们组成一个大小为 4×44\times4 的正方形。如下图。注意小 Z 不能旋转或者翻转这些碎片。

小 Z 得到如图 1 的碎片,然后经过重新排列得到图 2 的正方形。

由于小 Z 实在太笨了,聪明的你请写一个程序帮助他来解决这个问题吧。

输入格式

输入包含多组数据,请使用 EOF。

每组数据的的第一行包含一个正整数 nn,表示碎片的个数。接下来输入 nn 个碎片。每个碎片的第一行是两个正整数 rr 和 cc,表示这个碎片的行数和列数。接下来是 rr 行,每一行包含 cc 个字符0或1,1表示碎片占据这个位置,0表示该位置为空。数据保证每个碎片都是完整的一片(即1是相互连通的),并且没有行或者列全部为0。

输出格式

如果无法组成一个正方形,输出No solution;如果有多组解,输出Yes, many!。否则,输出Yes, only one!,接下来输出一个 4×44\times4 的矩阵 HH,HijH_{ij} 表示位置 i,ji,j 的碎片编号。碎片编号从 11 开始。

4
2 3
111
101
4 2
01
01
11
01
2 1
1 1
3 2
10
10
11
4
1 4
1111
1 4
1111
1 4
1111
1 4
1111
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001
Yes, only one!
1112
1412
3422
3442
Yes, many!
No solution

提示

数据范围

对于 30%30\% 的数据,n<5n < 5。

对于 100%100\% 的数据,n≤16n \leq 16。