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

小 Z 得到如图 1 的碎片,然后经过重新排列得到图 2 的正方形。
由于小 Z 实在太笨了,聪明的你请写一个程序帮助他来解决这个问题吧。
输入格式
输入包含多组数据,请使用 EOF。
每组数据的的第一行包含一个正整数 ,表示碎片的个数。接下来输入 个碎片。每个碎片的第一行是两个正整数 和 ,表示这个碎片的行数和列数。接下来是 行,每一行包含 个字符0或1,1表示碎片占据这个位置,0表示该位置为空。数据保证每个碎片都是完整的一片(即1是相互连通的),并且没有行或者列全部为0。
输出格式
如果无法组成一个正方形,输出No solution;如果有多组解,输出Yes, many!。否则,输出Yes, only one!,接下来输出一个 的矩阵 , 表示位置 的碎片编号。碎片编号从 开始。
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
提示
数据范围
对于 的数据,。
对于 的数据,。