BZPRO

#5156. [Tjoi2014]拼图

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

小Z最近迷上了拼图游戏，然而智商有限，他总是无法拼出完整图案。游戏是这样的：首先小Z会得到一些拼图碎片
，然后他试着重新排列这些碎片使得它们组成一个大小为4*4的正方形。如下图。注意小Z不能旋转或者翻转这些碎
片。
小Z得到如图1的碎片，然后经过重新排列得到图2的正方形。由于小Z实在太笨了，聪明的你请写一个程序帮助他来
解决这个问题吧。

输入格式

输入包含多组数据，请使用EOF。
每组数据的的第一行包含一个正整数N，表示碎片的个数。
接下来输入N个碎片。每个碎片的第一行是两个正整数r和c，表示这个碎片的行数和列数。
接下来是r行，每一行包含c个字符’0’或’1’
’1’表示碎片占据这个位置，’0’表示该位置为空。
数据保证每个碎片都是完整的一片(即’1’是相互连通的)，并且没有行或者列全部为’0’。
N<=16

输出格式

如果无法组成一个正方形，输出”No solution”；
如果有多组解，输出”Yes,many!”。否则，输出”Yes, only one!”
接下来输出一个 4 * 4 的矩阵 H，Hij表示位置 i, j 的碎片编号。碎片编号从 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

样例输出


			
Yes, only one!

1112

1412

3422

3442

Yes, many!

数据范围与提示

BZPRO Powered by Remmina.
Github Repository