Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## TLE的不行了,哪位大牛能帮忙看看代码啊

Posted by yzhw at 2009-03-26 18:15:27 on Problem 1069
```# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>
bool map1[51][51],map2[51][51];
int *list,num,n;
bool canput_sub(int r,int c,int len,int id1,int id2)
{
int i,j;
if(id2==1)
{

i=r;
for(j=c+i-r;j<=c+len-1;j++)
if(map1[i][j]) return 0;

}
else
{

for(i=r+len-1;i>=r;i--)
for(j=c;j<=c+i-r;j++)
if(map2[i][j]) return 0;

}
return 1;
}
void deput_sub(int r,int c,int len,int id1,int id2)
{
int i,j;
if(id2==1)
{
if(id1==1)
{
for(i=r;i<=r+len-1;i++)
{
for(j=c+i-r;j<=c+len-1;j++)
map1[i][j]=0;
}
}
else
{
for(i=r;i<=r+len-1;i++)
{
for(j=c+i-r;j<=c+len-1;j++)
map2[i][j]=0;
}
}
}
else
{
if(id1==1)
{
for(i=r;i<=r+len-1;i++)
for(j=c;j<=c+i-r;j++)
map1[i][j]=0;
}
else
{
for(i=r;i<=r+len-1;i++)
for(j=c;j<=c+i-r;j++)
map2[i][j]=0;
}
}
}
void put_sub(int r,int c,int len,int id1,int id2)
{
int i,j;
if(id2==1)
{
if(id1==1)
{
for(i=r;i<=r+len-1;i++)
{
for(j=c+i-r;j<=c+len-1;j++)
map1[i][j]=1;
}
}
else
{
for(i=r;i<=r+len-1;i++)
{
for(j=c+i-r;j<=c+len-1;j++)
map2[i][j]=1;
}
}
}
else
{
if(id1==1)
{
for(i=r;i<=r+len-1;i++)
for(j=c;j<=c+i-r;j++)
map1[i][j]=1;
}
else
{
for(i=r;i<=r+len-1;i++)
for(j=c;j<=c+i-r;j++)
map2[i][j]=1;
}
}
}
bool canput(int r,int c,int id,int len)
{
if(c+len-1>2*n||r+len-1>2*n) return 0;
if(id==1)
{
return canput_sub(r,c,len,1,1);
}
else
{
return canput_sub(r,c,len,2,2);
}
}
void put(int r,int c,int id,int len)
{
if(id==1)
{
put_sub(r,c,len,1,1);
put_sub(r,c+1,len-1,2,1);
}
else
{
put_sub(r,c,len,2,2);
put_sub(r+1,c,len-1,1,2);
}
}
void deput(int r,int c,int id,int len)
{
if(id==1)
{
deput_sub(r,c,len,1,1);
deput_sub(r,c+1,len-1,2,1);
}
else
{
deput_sub(r,c,len,2,2);
deput_sub(r+1,c,len-1,1,2);
}
}
bool dec(int r,int c,int id)
{
if(r>2*n) return 1;
else if(c>2*n&&id==1) return dec(r,1,2);
else if(c>2*n&&id==2) return dec(r+1,1,1);
else if(id==1&&map1[r][c]==1)
{
int i;
for(i=c;i<=2*n;i++)
if(!map1[r][i]) break;
return dec(r,i,id);
}
else if(id==2&&map2[r][c]==1)
{
int i;
for(i=c;i<=2*n;i++)
if(!map2[r][i]) break;
return dec(r,i,id);
}
else
{
int i;
for(i=1;i<=num;i++)
{
if(canput(r,c,id,list[i]))
{
put(r,c,id,list[i]);
if(dec(r,c+list[i],id))
return 1;
deput(r,c,id,list[i]);
}
else break;
}
return 0;
}
}
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int main()
{
int test,i;
scanf("%d",&test);
for(i=1;i<=test;i++)
{
int j,k,flag=0;
scanf("%d %d",&n,&num);
memset(map1,1,sizeof(map1));
memset(map2,1,sizeof(map2));
list=(int *)calloc(num+1,sizeof(int));
for(j=1;j<=num;j++) scanf("%d",list+j);
for(j=1;j<=num;j++)
{
if(n%list[j]==0)
{
flag=1;
break;
}
if(list[j]>n)
{
num=j-1;
break;
}
}
if(flag)
{
printf("YES\n");
free(list);
continue;
}
qsort(list+1,num,sizeof(int),cmp);
/*-------------set map----------------*/
for(j=1;j<=n+1;j++)
for(k=1;k<=j+n-1;k++)
map1[j][k]=0;
for(j=n+2;j<=2*n;j++)
for(k=j-n;k<=2*n;k++)
map1[j][k]=0;
for(j=1;j<=n;j++)
for(k=1;k<=j+n;k++)
map2[j][k]=0;
for(j=n+1;j<=2*n;j++)
for(k=j-n+1;k<=2*n;k++)
map2[j][k]=0;
/*----------end of build map--------*/
if(dec(1,1,1)) printf("YES\n");
else printf("NO\n");
free(list);

}

return 0;
}

```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator