背景 Background 潘帕斯草原最近流行起了一种拼图游戏，@潘帕斯雄鹰为了显示自己是最强的鹰，想尽办法要在这个游戏上赢过其他鹰…… 描述 Description 这个拼图游戏要求将一些图形拼成一个正方形，图形的个数从1到5。如下图所示，图形个数是4。图形不能旋转，拼的时候不能重叠，拼完后的正方形里面不能有空隙。所有给定的图形都要使用。左面的图表示这样拼不行，右面是一个成功的拼法。现在，@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰；如果可以，请输出一种完成这个游戏的方案。 输入格式 Input Format 文件的第一行是一个整数n，表示图形的个数，范围从1到5。接下来有n个部分，每个部分的第一行是2个整数i和j，表示下面的i行j列用来描述一个图形。图形用0和1表示，1表示图形占有这个位置，0表示不占有，中间没有空格。例如上图中图形A的描述是2 3111101所有图形的长与宽都不超过5。根据图形给出的顺序给每个图形编号，从1开始，至多到5。保证数据无多解情况。 输出格式 Output Format 如果不能拼成一个正方形，就输出"No solution possible"；否则，输出一种拼的方案：一个正方形的数阵，每个位置上的数字是占有这个位置的图形的编号，中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4，那么就可以输出1112141234223442 ///// 没什么好方法,穷举过了 #include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#define MAX 10int gm[10][10][10]={0},gmfig[10][2],gn;int gfig[MAX][MAX]={0}; int move(int k,int *x, int *y){ int xt,yt,xg,yg,i,j; for(xt=*x,yt=*y; xt<=gn || yt<=gn;){ if(xt>gn){ xt=1; yt++; } for(i=1,yg=yt; yg<=gn && i<=gmfig[k][0]; i++,yg++){ for(j=1,xg=xt; xg<=gn && j<=gmfig[k][1]; j++,xg++){ if( gm[k][i][j] && gfig[yg][xg] ) goto next; } if(j<=gmfig[k][1]) goto next; } if(i<=gmfig[k][0]) goto next; for(i=1,yg=yt; yg<=gn && i<=gmfig[k][0]; i++,yg++) for(j=1,xg=xt; xg<=gn && j<=gmfig[k][1]; j++,xg++){ if(gm[k][i][j]) gfig[yg][xg]=gm[k][i][j]; } *x = xt+1; *y = yt; return 1;next: xt++; } return 0;}int get(){ int k,save[MAX][MAX],x,y; for(k=1; k<=gmfig[0][0]; k++){ if(!gm[k][0][0]) break; } if(k>gmfig[0][0]) return 1; for(k=1; k<=gmfig[0][0]; k++){ if(gm[k][0][0]) continue; memcpy(save,gfig,sizeof(int)*MAX*MAX); gm[k][0][0]=1; for(x=y=1; move(k,&x,&y);){ if(get()) return 1; else memcpy(gfig,save,sizeof(int)*MAX*MAX); } gm[k][0][0]=0; } return 0;}int main(){ int i,j,it,jt,k,n; char str[20]; scanf("%d",&gn); gmfig[0][0]=gn; for(n=0,k=1; k<=gn; k++){ scanf("%d %d",&i,&j); gmfig[k][0]=i; gmfig[k][1]=j; for(it=1; it<=i; it++){ scanf("%s",str); for(jt=0; jt<j; jt++) if(str[jt]=='1'){ gm[k][it][jt+1]=k; n++; } } } gn=(int)sqrt(n); if(gn*gn != n) printf("No solution possible\n"); else if(gn==1) printf("1"); else{ if(get()) for(it=1; it<=gn; it++){ for(jt=1; jt<=gn; jt++) printf("%d",gfig[it][jt]); printf("\n"); } else printf("No solution possible\n"); } return 0;}
评论