zju 1017 "百慕大魔鬼三角的蛋糕" 总是超时,该如何解决

zju 1017 "百慕大魔鬼三角的蛋糕" 总是超时
这道题提交的时候总是超时,   一般的数据都能过,   但当a> =20,就基本上开始超时了.哪位有通过了的,给讲讲吧.

我的方法就是狂搜加贪心.   把所要用到的切割三角形按边长从大到小排,先用大的三角形去切割.   然后用二维数组装六边形中所有三角形,正三角标为1,倒三角标为-1,其他没有三角的地方为0.   然后从上到下,从左到右开始搜.在对每个还未被切割的位置进行搜索时,先算出其能扩张的最大三角形边数,以便与切割的三角形边长进行比较.

当遇到的三角形a是正三角时,他只能构造更大的正三角形,且a位于这个大三角形最顶部;   当遇到的三角形b是倒三角时,他只能构造更大的倒三角,且b位于这个大三角的最左上部.

有什么可以剪枝的方法吗?

------解决方案--------------------
我直接抄书上的答案，还没仔细研究过
#include <iostream.h>

int L;
int n;
char ok[51];
int type[51];
int square[51];
int zero;
char reachable[4000];
char board[60][110];

struct node{
int x,y;
}stack[1000];

void input(){
int i;
cin> > L> > n;
for(i=0;i <52;i++) ok[i]=0;
for(i=0;i <n;i++){
cin> > type[i];
ok[type[i]]=1;
}
n=0;
for(i=0;i <51;i++){
if(ok[i]){
type[n]=i;
square[n++]=i*i;
}
}
}

int cal(int x,int y){
int tx,ty,i,j;
if((x+y)%2){
for(i=0;;i++)
for(j=y-i;j <=y+i;j++)
if(board[x+i][j])return i;
}else{
for(i=0;;i++){
tx=x+i;
ty=y+i;
for(j=0;j <2*i+1;j++){
if(board[tx][ty])return i;
if(j%2)ty++;
else tx--;
}
}
}
}

void color_tri(int x,int y,int l,char color){
int i,j,tx,ty;
if((x+y)%2){
for(i=0;i <l;i++)
for(j=y-i;j <=y+i;j++)
board[x+i][j]=color;
}else{
for(i=0;i <l;i++){
tx=x+i;
ty=y+i;
for(j=0;j <2*i+1;j++){
board[tx][ty]=color;
if(j%2)ty++;
else tx--;
}
}
}
}

void color_line(int x,int y,int l,char color){
int i,j,tx,ty;
if((x+y)%2){
i=l-1;
for(j=y-i;j <=y+i;j++)
board[x+i][j]=color;
}else{
i=l-1;
tx=x+i;
ty=y+i;
for(j=0;j <2*i+1;j++){
board[tx][ty]=color;
if(j%2)ty++;
else tx--;
}
}
}

int search(int step){
int x,y;
int i,maxl;
x=stack[step-1].x;
y=stack[step-1].y;
while(x <2*L){
if(board[x][y])y++;
else break;
if(y> 100){
x++;
y=0;
}
}
if(x> =2*L)return 1;

maxl=cal(x,y);
color_tri(x,y,maxl,1);
zero-=maxl*maxl;
stack[step].x=x;
stack[step].y=y;

for(i=maxl;i> =2;i--){
if(ok[i] && reachable[zero] && search(step+1)) return 1;
color_line(x,y,i,0);
zero+=(2*i-1);
}
board[x][y]=0;
zero++;
return 0;
}

int possible(){
int i,j;
for(j=0;j <n;j++)
if(L%type[j]==0) return 1;

for(i=0;i <=L;i++) reachable[i]=0;
reachable[0]=1;
for(i=0;i <=L;i++){
if(reachable[i]){
for(j=0;j <n;j++){
if(i+type[j] <=L)reachable[i+type[j]]=1;
}
}
}
if(!reachable[L])return -1;

for(i=0;i <=6*L*L;i++){
if(reachable[i]){
for(j=0;j <n;j++){
if(i+square[j] <=6*L*L)reachable[i+square[j]]=1;
}
}
}
if(!reachable[6*L*L])return -1;
return 0;
}

void init(int type){
int i,j;
for(i=0;i <60;i++)
for(j=0;j <110;j++)
board[i][j]=1;

zero=0;
if(type> =1){
color_tri(0,25,L,0);
zero+=L*L;
}
if(type> =2){
color_tri(0,26,L,0);