问题 24704. -- 【2014赛前模拟三】拼图

24704: 【2014赛前模拟三】拼图

时间限制: 5 Sec  内存限制: 256 MB
献花: 2  解决: 2
[献花][花圈]

题目描述

3.拼图[puzzling. pas/c/cpp]

 

【问题描述】

拼图游戏要求将一些图形拼成一个正方形,图形的个数从15。如下图所示,图形个数是4


图形不能旋转,拼的时候不能重叠,拼完后的正方形里面不能有空隙。所有给定的图形都要使用。

左面的图表示这样拼不行,右面是一个成功的拼法。

【输入数据】

文件的第一行是一个整数n,表示图形的个数,范围从15

接下来有n个部分,每个部分的第一行是2个整数ij,表示下面的ij列用来描述一个图形。图形用01表示,1表示图形占有这个位置,0表示不占有,中间没有空格。例如上图中图形A的描述是”:

2 3

111

101

所有图形的长与宽都不超过5。

根据图形给出的顺序给每个图形编号,从1开始,至多到5

保证数据无多解情况。

【输出数据】

  如果不能拼成一个正方形,就输出No solution possible;否则,输出一种拼的方案:一个正方形的数阵,每个位置上的数字是占有这个位置的图形的编号,中间没有空格。例如上面ABCD的编号依次是1234,那么就可以输出

1112

1412

3422

3442

 

【输入样例1

4

1 4

1111

1 4

1111

1 4

1111

2 3

111

001

 

【输出样例1

No solution possible

 

【输入样例2

5

2 2

11

11

2 3

111

100

3 2

11

01

01

1 3

111

1 1

1

 

【输出样例2

1133

1153

2223

2444

 

输入

输出

提示

来源

[献花][花圈]