Problem: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1017
这是什么题呢。个人觉得，是一道编程题，大概大很久之前想跳过这题。现在也明白原因了，它没有用很花哨的算法，也没有非常复杂的数学定理。但是它难在哪里呢？是的，是实现。在做出这题后，我觉得最难的是实现，而且它的设计还的确需要一些Design Pattern里的东东。
解决这个题的关键是重新建立坐标系，准确无误的标识出 1. 原来的六边形 2. 将要被放进来的三角形 3. 当前是否可以放入某一种类型的三角形 4. 更新当前的状态，在放入某一种三角形之后。
这样来建立坐标系。首先观察图1. 1019.1。 可以看到所有的三角形事实上只有两种，一种头向上，一种头向下。如果我们能用一种新的方式来标识任何一个最小的三角形，我的问题基本就解决了。观察图2， 1019.2。黑的三角形和白色的三角形都可以用这样的方式来标识。比如三角型 (0,0), (1,0), (0,1) 实际上就是四边形(0,0), (1,0),(1,1), (0,1)其中的一半，而另一个三角形(0,1), (1,1), (1,0) 是另一半。而我们可以通过任何一个三角形所在的四边形的左下点再加上一个朝向来表示是哪一个三角形。比如三角形 (3,4) ,(4,3),(4,4)就可以用(3,3, 0)表示，这个坐标表示。它是以(3,3)为顶点， 而且是头向下的那一个三角形来唯一表示。
而在实现的时候，直接将所有向上和向下的三角形放在两个数组里来记录hex[0]和hex[1]分别track头向下和头向上的三角形。参见图 1019.3 。
有了这种表示。所有的事情就会方便一些。接下来，只要实现一个对N长等边三角形进行拆解过程就可以了。如果判断一个N长的三角形是否可以放进当前的画布，只要看看它的所有子三角形是否已经被占用就可以了。实现中的Iterate就是这个作用。它可以实现一次对给定长度和朝向的三角形的子三角形进行一次遍历。而遍历时做什么，则是灵活的。可以是Seter，把所有的子三角形设置成1 (表示占用)。Cleaner，把所有的子三角形设置成0(表示空数)。以及Checker来检查是否可以所有的子三角形都未被占用。
有了所有的这些，实现就相对容易了。
1. 把所有的可能三角形排序，如果后面的长度是前面的某一个长度的N倍，则去掉。因为它可以用前的三角形表示。另外，如果三边形长度是len，而其中有某一个长度正好可以除尽，则返回YES。
2. 初始化三边形。比如一个长度为len的六边形，可以这样来表示。它可以是正方形（新的坐标系里的正方形） (0,0) 长度是len再减去三角形(0,0, 1, len)和 (len, len, 0, len)，其中头两个数表示三角形所在的四边形左下顶点，第三个元素表示三角形头是否朝上(只有0，1), 第四个元素表示这个等边三角形的长度。比如(0,0, 1, len)实际表示三角形(0,0),(0,len),(len,0). 只要把这两个三角形表示成占用做为初始状态。那么实际上就表示了六边形。
3. 递归所有的可能解。这一步还是很关键的。参数很重要，实际上也决定了递归的顺序。我的基本想法是, 一层一层向上排，当前这一层先排向上的三角形，再排向下的三角形。给定一个坐标点，(x,y)以及另一个参数up，来表示当前排向上的三角形还是向下的三角形。如果up=true，那么，我假设所有的小于y的层都已经被放满了，同时，当前这一层中向上的三角形里小于x的也都被放满了。然后向x的正向找下一个空的位置。如果没有了，说明这一层都排满了，接着开始排当前这一层头向下的三角形。如果up=false，也是类似。停卡的条件是所有的层都被排满。直接返回true. 如果所有的可能都没有返回false.
//=========================================================================
// ZOJ Problem No.1017
// Auther: Jonas, Yang
// Mail : jonas.yang.jun@gmail.com
// Data : Mar.19.2011
// Performance Status:
// Running time | Memory | Language
// 0.26s | 188K | C++
//=========================================================================
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
class BTriangle
{
public:
int len;
vector<int> subTris;
vector<vector<int> > hex[2];
class Functor
{
public:
vector<vector<int> > * hex;
virtual bool operator()(int x, int y, bool up){ return false;};
};
class Checker: public Functor
{
public:
Checker(vector<vector<int> > * _hex) { hex = _hex;};
bool operator()(int x, int y, bool up)
{
return (*(hex + up))[x][y] == 0;
}
};
class Cleaner: public Functor
{
public:
Cleaner(vector<vector<int> > * _hex) { hex = _hex;}
bool operator()(int x, int y, bool up)
{
(*(hex + up))[x][y] = 0;
return true;
}
};
class Seter: public Functor
{
public:
Seter(vector<vector<int> > * _hex) { hex = _hex;}
bool operator()(int x, int y, bool up)
{
(*(hex + up))[x][y] = 1;
return true;
}
};
Seter seter;
Checker checker;
Cleaner cleaner;
bool Iterate(int x, int y, int length, bool bUp, Functor & f)
{
for ( int i = 0; i < length; ++i ) {
int xStart = bUp ? x : x + i;
int yStart = bUp ? y + i : y + length - i - 1;
for ( int j = 0; j < length - i; ++j ) {
if ( bUp ) {
if ( !f(xStart + j, yStart, true) ) {
return false;
}
if ( j < length - i - 1 && !f(xStart + j, yStart, false)) {
return false;
}
} else {
if ( !f(xStart + j, yStart, false) ) {
return false;
}
if ( j > 0 && !f(xStart + j, yStart, true)) {
return false;
}
}
}
}
return true;
}
BTriangle():seter(Seter(hex)), cleaner(Cleaner(hex)), checker(Checker(hex))
{
cin >> len;
int N;
cin >> N;
subTris.resize(N);
for ( int i = 0; i < N; ++i ) {
cin >> subTris[i];
}
}
bool IsAcceptable(int x, int y, int length, bool bUp )
{
if ( x < 0 || y < 0 || x + length > hex[0].size() || y + length > hex[0].size() ) {
return false;
}
return Iterate(x, y, length, bUp, checker);
}
bool FillHex(int x, int y, bool bUp)
{
if ( y >= hex[1].size() ) {
return true;
}
if ( bUp ) {
while ( x < hex[1].size() ) {
if ( !hex[1][x][y] ) {
break;
}
x ++;
}
if ( x == hex[0].size() ) {
return FillHex(0, y, false);
}
for ( int i = 0; i < subTris.size(); ++i ) {
if ( IsAcceptable(x, y, subTris[i], true) ) {
Iterate(x, y, subTris[i], true, seter );
if ( FillHex(x + subTris[i], y, bUp) ) {
return true;
}
Iterate(x, y, subTris[i], true, cleaner );
}
}
} else {
while( x < hex[0].size() ) {
if ( !hex[0][x][y] ) {
break;
}
x ++;
}
if ( x == hex[0].size() ) {
return FillHex(0, y + 1, true);
}
for ( int i = 0; i < subTris.size(); ++i ) {
if ( IsAcceptable(x - subTris[i] + 1, y, subTris[i], false) ) {
Iterate(x - subTris[i] + 1, y, subTris[i], false , seter);
if (FillHex(x + 1, y, false)) {
return true;
}
Iterate(x - subTris[i] + 1, y, subTris[i], false, cleaner);
}
}
}
return false;
}
bool IsDevided()
{
// Refine subTris
sort(subTris.begin(), subTris.end());
// Check whether there is dividable side in subTris. If so, return true.
{
int i = 0;
for (; i < subTris.size() && subTris[i] <= len; ++i ) {
if (!(len % subTris[i])) {
return true;
}
}
subTris.erase(subTris.begin() + i, subTris.end());
}
vector<int> subRefined;
for ( int i = 0; i < subTris.size(); ++i ) {
int j = 0;
for ( ; j < i; ++j ) {
if (!(subTris[i] % subTris[j])) {
break;
}
}
if ( j == i ) {
subRefined.push_back(subTris[i]);
}
}
subTris = subRefined;
{
hex[0].resize(len * 2 , vector<int>(len * 2, 1));
hex[1].resize(len * 2, vector<int>(len * 2, 1));
Iterate(0, 0, len, true , cleaner );
if ( FillHex(0, 0, true) ) {
return true;
}
}
{
hex[0].resize(len * 2 , vector<int>(len * 2, 1));
hex[1].resize(len * 2, vector<int>(len * 2, 1));
Iterate(0, 0, len, true , cleaner );
Iterate(0, 0, len, false , cleaner );
if ( FillHex(0, 0, true) ) {
return true;
}
}
{
hex[0].resize(len * 2 , vector<int>(len * 2, 1));
hex[1].resize(len * 2, vector<int>(len * 2, 1));
Iterate(0, 0, len, true , cleaner );
Iterate(0, 0, len, false , cleaner );
Iterate(0, len, len, true , cleaner );
if ( FillHex(0, 0, true) ) {
return true;
}
}
{
hex[0].resize(len * 2 , vector<int>(len * 2, 0));
hex[1].resize(len * 2, vector<int>(len * 2, 0));
Iterate(0, 0, len, true , seter );
Iterate(len, len, len, false , seter );
if ( FillHex(0, 0, true) ) {
return true;
}
}
return false;
}
};
int main()
{
int caseCnt = 0;
cin >> caseCnt;
while( caseCnt-- > 0 ) {
BTriangle bt;
if (bt.IsDevided()) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
