[TJOI2014] 拼图
题目描述
小Z最近迷上了拼图游戏,然而智商有限,他总是无法拼出完整图案。游戏是这样的：首先小Z会得到一些拼图碎片,然后他试着重新排列这些碎片使得它们组成一个大小为4\*4的正方形。如下图。注意小Z不能旋转或者翻转这些碎片。
小Z得到如图1的碎片,然后经过重新排列得到图2的正方形。
由于小Z实在太笨了,聪明的你请写一个程序帮助他来解决这个问题吧。
输入输出格式
输入格式
输入包含多组数据,请使用EOF
每组数据的的第一行包含一个正整数N，表示碎片的个数。接下来输入N个碎片。每个碎片的第一行是两个正整数r和c,表示这个碎片的行数和列数。接下来是r行,每一行包含c个字符'0'或'1'，'1'表示碎片占据这个位置,'0'表示该位置为空。数据保证每个碎片都是完整的一片(即'1'是相互连通的),并且没有行或者列全部为'0'。
输出格式
如果无法组成一个正方形,输出”No solution”;如果有多组解,输出”Yes, many!”。否则,输出”Yes, only one!”,接下来输出一个4\*4的矩阵H,Hij表示位置i,j的碎片编号。碎片编号从1开始。
输入输出样例
输入样例 #1
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输出样例 #1
Yes, only one!
1112
1412
3422
3442
Yes, many!
No solution说明
### 数据范围
对于 30% 的数据，N < 5
对于 100% 的数据，N ≤ 16