# 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;
}

• 回溯+剪枝,还是挂..汗 (5473) yzhw 2009-03-26 18:18:35