本来是个水题，我一交，WA：90，第一点错误，答案1位选手输出20位。
得，骗数据，共1个物体，4*4大小，推断可能是：
1
4 4
1000
0000
0000
0000
这叫什么数据。。
一定要注意可能n*m的方块没有占用n*m的情况，于是乎，我放上来了
MYCODE:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <stdio.h> //#define dd int a,b;for (a=1;a<=ls;a++){for (b=1;b<=ls;b++)printf("%1d",chr[a][b]);printf("\n");}printf("\n"); int pie[6][7][6];//pie[i][6][1]=h;pie[i][6][2]=w; int n,nn,ls;//nn:总块数 ;ls:正方形边长 int chr[6][6]; inline void set(int x,int y,int k,int mu){//mu=1 add;mu=-1 delete int i,j; for (i=1;i<=pie[k][6][1];i++) for (j=1;j<=pie[k][6][2];j++) chr[x+i-1][y+j-1]+=pie[k][i][j]*mu; } int rig(){ static int i,j; for (i=1;i<=ls;i++) for (j=1;j<=ls;j++)if (chr[i][j]>1)return 0; return 1; } inline int find(int k) { //dd int i,j; if (k>n){memset(chr,0,sizeof(chr)); return (1); } for (i=1;pie[k][6][1]+i-1<=ls;i++) for (j=1;pie[k][6][2]+j-1<=ls;j++){ set(i,j,k,1); if (rig()==1&&find(k+1)==1){ set(i,j,k,k); //printf("%4d%4d%4d\n",i,j,k); //dd return (1); } else set(i,j,k,-1); } return 0; } int main(){ int i,j,k,l; int w,h; scanf("%d",&n); for (i=1;i<=n;i++){ scanf ("%d %d\n",&h,&w); for (j=1;j<=h;j++) for (k=1;k<=w;k++){ scanf("%1d",&pie[i][j][k]); nn+=pie[i][j][k]; } l=0; while(l==0){for (j=1;j<=w;j++)if (pie[i][h][j]>0){ l=1;break;}if (l==0)h--;else break;}l=0; while(l==0){for (j=1;j<=h;j++)if (pie[i][j][w]>0){ l=1;break;}if (l==0)w--;else break;}//鬼知道4*4网格只有(1,1)=1为什么合法 pie[i][6][1]=h;pie[i][6][2]=w; //printf("%4d %4d",w,h); } ls=sqrt(nn); if (ls*ls!=nn){printf("%s","No solution possible");return 0;}//ls*ls!=nn表明不能拼成正方形 if (find(1)==0)printf("%s","No solution possible"); else for (i=1;i<=ls;i++){for (j=1;j<=ls;j++)printf("%1d",chr[i][j]);printf("\n");} //getch(); return 0; } |
题目:拼图
题目描述
背景
潘帕斯草原最近流行起了一种拼图游戏，@潘帕斯雄鹰为了显示自己是最强的鹰，想尽办法要在这个游戏上赢过其他鹰……
题目描述
这个拼图游戏要求将一些图形拼成一个正方形，图形的个数从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 拼图 回溯题解