| 背景 Background | |||
| 潘帕斯草原最近流行起了一种拼图游戏，@潘帕斯雄鹰为了显示自己是最强的鹰，想尽办法要在这个游戏上赢过其他鹰…… | |||
| 描述 Description | |||
这个拼图游戏要求将一些图形拼成一个正方形，图形的个数从1到5。如下图所示，图形个数是4。 图形不能旋转，拼的时候不能重叠，拼完后的正方形里面不能有空隙。所有给定的图形都要使用。  左面的图表示这样拼不行，右面是一个成功的拼法。 现在，@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰；如果可以，请输出一种完成这个游戏的方案。 | |||
| 输入格式 Input Format | |||
| 文件的第一行是一个整数n，表示图形的个数，范围从1到5。 接下来有n个部分，每个部分的第一行是2个整数i和j，表示下面的i行j列用来描述一个图形。图形用0和1表示，1表示图形占有这个位置，0表示不占有，中间没有空格。例如上图中图形A的描述是 2 3 111 101 所有图形的长与宽都不超过5。 根据图形给出的顺序给每个图形编号，从1开始，至多到5。 保证数据无多解情况。 | |||
| 输出格式 Output Format | |||
| 如果不能拼成一个正方形，就输出"No solution possible"；否则，输出一种拼的方案：一个正方形的数阵，每个位置上的数字是占有这个位置的图形的编号，中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4，那么就可以输出 1112 1412 3422 3442 | |||
///// 没什么好方法,穷举过了
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 10
int 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;
}
评论