triangle.cpp

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

#include <fstream.h>

ifstream in("Triangle.in");
ofstream out("Triangle.out");

int  L;                 //六边形的边长
int  n;                 //小三角形的边长
char ok[51];           //ok[i]表示边长为i的三角形是否可用
int  type[51];         //type[i]储存第i种三角形的边长
int  square[51];       //square[i]储存第i种三角形的面积
int  zero;              //尚未覆盖的面积
char reachable[4000]; //reachable[i]：面积i是否可由合法三角形面积组合得到
char board[60][110];  //坐标化后的六边形的相应坐标位置是否已经给覆盖

struct node {
    int x,y;
}   stack[1000];         //保存搜索第i层用于覆盖的三角形的顶点坐标

//输入数据
void input()            
{
  int  i;
  in >> L >> n;
  for (i=0; i<51; i++) ok[i]=0;
  for (i=0; i<n; i++)
  {
    in >> type[i];
    ok[type[i]]=1;
  }
  n=0;
  for (i=0; i<51; i++)
  {
    if (ok[i])
    {
      type[n]=i;
      square[n++]=i*i;
    }
  }
}

//返回以坐标(x,y)为顶点可以覆盖的最大三角形的边长
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--;
      }
    }
  }
}

//将以坐标(x,y)为顶点的边长为l的三角形涂色color。
//color=1时：相当于在坐标(x,y)的地方覆盖一个边长为l的三角形；
//color=0时：相当于去掉原先以坐标(x,y)为顶点的边长为l的三角形。
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--;
      }
    }
  }
}

//将以坐标(x,y)为顶点的边长为l的三角形的底边涂色color。
//color=1时：以坐标(x,y)为顶点覆盖的三角形由原来边长(l-1)变成l；
//color=0时：以坐标(x,y)为顶点覆盖的三角形由原来边长l变成(l-1)；
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，y为上次放置三角形的坐标
  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--)
  {
    //存在边长为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;
}

//对输入进行一些预处理
//确定有解，return 1；
//确定无解，return -1；
//还无法确定，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++) reachable[i]=0;
  reachable[0]=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);
    zero+=L*L;
  }
  if (type>=3)
  {
    color_tri(0,25+2*L,L,0);
    zero+=L*L;
  }
  if (type>=4)
  {
    color_tri(L,25-L+1,L,0);
    color_tri(L,25+L,L,0);
    color_tri(L,25+L+1,L,0);
    zero+=3*L*L;
  }
  stack[0].x=0;
  stack[0].y=25;
}

int main()
{
  int cases;
  in >> cases;
  while (cases--)
  {
    input();
    switch (possible())
    {
      case 1: 
        out << "YES" << endl;
        break;
      case -1:
        out << "NO" << endl;
        break;
      default:
        init(1);    //六边形的1/6能否可以完全覆盖
        if (search(1)) 
        {
       	  out << "YES" << endl; 
          break;
        }
        init(2);    //六边形的1/3能否可以完全覆盖
        if (search(1)) 
        {
      	  out << "YES" << endl;
      	  break;
        }
        init(3);    //六边形的1/2能否可以完全覆盖
        if (search(1)) 
        {
          out << "YES" << endl;
      	  break;
        }
        init(4);    //六边形的全部能否可以完全覆盖
        if (search(1)) 
        {
      	  out << "YES" << endl;
      	  break;
        } 
        out << "NO" << endl;
    }
  }
  return 0;
}