p44 拼图 回溯题解

本来是个水题,我一交,WA:90,第一点错误,答案1位选手输出20位。
得,骗数据,共1个物体,4*4大小,推断可能是:

1
4 4
1000
0000
0000
0000

这叫什么数据。。
一定要注意可能n*m的方块没有占用n*m的情况,于是乎,我放上来了
MYCODE:

题目:拼图

问题编号:44

题目描述

背景
潘帕斯草原最近流行起了一种拼图游戏,@潘帕斯雄鹰为了显示自己是最强的鹰,想尽办法要在这个游戏上赢过其他鹰……

题目描述
这个拼图游戏要求将一些图形拼成一个正方形,图形的个数从1到5。如下图所示,图形个数是4。

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

左面的图表示这样拼不行,右面是一个成功的拼法。
现在,@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰;如果可以,请输出一种完成这个游戏的方案。

输入格式

文件的第一行是一个整数n,表示图形的个数,范围从1到5。
接下来有n个部分,每个部分的第一行是2个整数i和j,表示下面的i行j列用来描述一个图形。图形用0和1表示,1表示图形占有这个位置,0表示不占有,中间没有空格。例如上图中图形A的描述是
2 3
111
101
所有图形的长与宽都不超过5。
根据图形给出的顺序给每个图形编号,从1开始,至多到5。
保证数据无多解情况。

输出格式

如果不能拼成一个正方形,就输出“No solution possible”;否则,输出一种拼的方案:一个正方形的数阵,每个位置上的数字是占有这个位置的图形的编号,中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4,那么就可以输出
1112
1412
3422
3442

样例输入

样例输出

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: p44 拼图 回溯题解

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据