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

## 回溯+剪枝,还是挂..汗

Posted by yzhw at 2009-03-26 18:18:35 on Problem 1069
In Reply To:TLE的不行了,哪位大牛能帮忙看看代码啊 Posted by:yzhw at 2009-03-26 18:15:27
```> # 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:

User ID:
Title:

Content: