forestkeeper

C++博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
题意是一个覆盖问题,用n个各种边长的小三角形来覆盖一个六边形,基本上可以直接深搜,可以试着覆盖六分之一,三分之一和二分之一至全部,四种覆盖形式有一种达到完全覆盖即可退出,以此来降低复杂度。

对三角形坐标的表示上采用了如下的表示法:

                                                                 
以这种方式来表示整个六边形上的三角形(图画的比较省略。。因为我只会用画图。。。。)

这题主要的难点不在思路,而在coding
#include<iostream>
#include
<cstring>
using namespace std;
int l,n;
int t[10];
bool b[60][110];
bool used[26];
bool square_vis[6*25*25+1];
int zero;
struct node
{
    
int x;
    
int y;
}
 stack[1000];
void flood_line(int x,int y,int l,int c)
{
    
int i,j;
    
int tx,ty;
    
if ((x+y)%2)
    
{
        i 
= l-1;
        
for (j=y-i; j<=y+i; j++)
           b[x
+i][j] = c;        
    }

    
else
    
{
        i 
= l-1;
        tx 
= x+i;
        ty 
= y+i;
        
for (j=0; j<2*i+1; j++)
        
{
            b[tx][ty] 
= c;
            
if (j%2)ty++;
            
else tx--;
        }

    }

}

void flood(int x,int y,int l,int c)
{
    
if ((x+y)%2)
    
{
        
for (int i=0; i<l; i++)
         
for (int j=y-i; j<=y+i; j++)
           b[x
+i][j] = c;
    }

    
else
    
{
        
for (int i =0; i<l; i++)
        
{
            
int tx = x+i;
            
int ty = y+i;
         
for (int j=0; j<2*i+1; j++)
         
{
            b[tx][ty] 
= c;
            
if(j%2)
             ty
++;
             
else tx--;
         }

        }

    }

}

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(b[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 (b[tx][ty])
                  
return i;
                
if (j%2)
                  ty
++;
                  
else tx--;
            }

        }

    }

}

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

    }

    
if (x>=2*l)
     
return true;
    maxl 
= cal(x,y);
    flood(x,y,maxl,
1);
    zero 
-= maxl*maxl;
    stack[step].x
= x;
    stack[step].y 
= y;
    
    
for (i=maxl; i>=2; i--)
    
{
     
if(used[i]&&square_vis[zero]&&search(step+1))
       
return true;
       flood_line(x,y,i,
0);
       zero
+=(2*i-1);
    }

    b[x][y] 
= 0;
    zero
++;
    
return false;
}

void init()
{
    memset(used,
false,sizeof(used));
    cin 
>> l;
    cin 
>> n;
    
for (int i=0; i<n; i++)
    
{
      cin 
>> t[i];
      used[t[i]] 
= true;
    }

    n 
= 0;
    
for (int i=1; i<=l; i++)
     
if (used[i])
         t[n
++= i;
}

void run()
{
    
for(int i=0; i<n; i++)
     
if(l%t[i]==0)
     
{
         cout 
<< "YES"<<endl;
         
return;
     }

    
bool length_vis[26];
    memset(length_vis,
false,sizeof(length_vis));
    length_vis[
0= true;
    
for (int i = 0; i<=l; i++)
    
if (length_vis[i])
      
for (int j=0; j<n; j++)
       
if (i+t[j]<=l)
         length_vis[i
+t[j]] = true;
   
if (!length_vis[l])
   
{
          cout 
<< "NO"<<endl;
          
return;
   }

   memset(square_vis,
false,sizeof(square_vis));
   square_vis[
0= true;
   
for (int i=0; i<=6*l*l; i++)
   
if (square_vis[i])
     
for (int j=0; j<n; j++)
      
if (i+t[j]*t[j]<=6*l*l)
        square_vis[i
+t[j]*t[j]]= true;
   
if (!square_vis[6*l*l])
   
{
          cout 
<< "NO"<<endl;
          
return;
   }

   memset(b,
true,sizeof(b));
   flood(
0,25,l,0);
   zero 
= l*l;
   stack[
0].x = 0;
   stack[
0].y = 25;
   
if (search(1))
   
{
          cout 
<< "YES"<<endl;
          
return;
   }

   memset(b,
true,sizeof(b));
   flood(
0,25,l,0);
   flood(
0,26,l,0);
   zero 
= l*l*2;
   
if (search(1))
   
{
          cout
<< "YES"<<endl;
          
return;
   }

   memset(b,
true,sizeof(b));
   flood(
0,25,l,0);
   flood(
0,26,l,0);
   flood(
0,25+2*l,l,0);
   zero 
= l*l*3;
   
if (search(1))
   
{
          cout 
<< "YES"<<endl;
          
return;
   }

   memset(b,
true,sizeof(b));
   flood(
0,25,l,0);
   flood(
0,26,l,0);
   flood(
0,25+2*l,l,0);
   flood(l,
25-l+1,l,0);
   flood(l,
25+l,l,0);
   flood(l,
25+l+1,l,0);
   zero 
= 6*l*l;
   
if (search(1))
   
{
         cout 
<< "YES"<<endl;
         
return
   }

   cout 
<< "NO"<<endl;
   
return;
}

int main()
{
    
int cas;
    cin 
>> cas;
    
while(cas--)
    
{
    init();
    run();
    }

}


posted on 2010-01-08 10:32 forestkeeper 阅读(1382) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理