| Comments

ZOJ2673

Hexagon and Rhombic Dominoes

A regular hexagon with side length n is divided into 6n2 unit triangles.

1

Your task is to cover it with rhombic dominoes — pieces composed of two unit triangles sharing a side.

2

Each domino must be placed in such a way, that it covers exactly two unit triangles. No triangle must be covered with more than one domino.

Count the number of ways to do so. For example there are two ways to cover a hexagon with side length~1, they are shown on the picture.

3

Input

Eace re several test cases in the input. Each case contains n ( 1 <= n <= 7 ). There is an empty line between each case. Output

Output
the number of ways to cover hexagon with rombic dominoes. There should be an empty line between each case. Example

Input 1
2
Output
2
20

题意
由6n2个三角形组成的正6边形 ，分成 2个三角形组成的菱形 ，一共有多少种分法
类似的拼图形的题目一般都是搜索加dp。因为 n 最大为 7 若用 0和1表示每个三角形是否被填充 最大的状态 有 22*7 那么多 。然后从上到下，最多7层。（因为图形是对称的，所以只算一半）。
假设上一层倒着放的三角形都已经被填满，上一层没有被放的正着放的三角形在这一层就会被这一层对应位置的倒着的三角形结合。 上一层放了 则 可以和这一层的左边或者右边的三角形结合。（晕）

dp[i][j] =∑dp[i-1][m] 满足m状态能转换成j状态。

初始化有看不见的第0层全部放满。

结果则是最后一层没有放满的平方和。∑dp[n][m]*dp[n][m]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
typedef  long long LL;

#define clr(x) memset((x),0,sizeof(x))
#define inf 0x3f3f3f3f

using namespace std;
LL dp[10][1<<16];
bool vis[10][1<<16];
int n;
int no;
vector <int > re;
bool revis[1<<16];
void dfs(int dep,int st,int nest)
{
    if(dep>(n+no-2))
    {
        if(!revis[nest])
        {
            revis[nest] =1;
            re.push_back(nest);
        }
        if(!vis[no][nest])
        {
            vis[no][nest]=1;
            dp[no][nest] += dp[no-1][st];
        }
        //dp[no][nest] ++;
        return ;
    }
    if((st&(1<<dep))==0)
    {
        dfs(dep+1,st,nest);
    }else {
        if((nest&(1<<dep))==0)
        dfs(dep+1,st,nest|(1<<dep));
        dfs(dep+1,st,nest|(1<<(dep+1)));
    }

}

int main()
{
    int cas = 1;
    while(~scanf("%d",&n))
    {
        no = 1;
        memset(dp,0,sizeof dp);
        re.clear();
        dp[0][(1<<n)-1] =1;
        dfs(0,((1<<n)-1),0);
        for(int i =2;i<=n;i++)
        {
            no = i;
            vector <int > tmp = re;
            re.clear();
            memset(revis,0,sizeof revis);
            for(int j = 0;j <tmp.size();j++)
            {
              //  printf("%d*%d ",dp[no-1][tmp[j]],tmp[j]);
                memset(vis[no],0,sizeof vis[no]);
                dfs(0,tmp[j],0);
            }
            //printf("\n");
        }
        LL ans = 0;
        for(int i=0;i<re.size();i++)
        {
            //printf("%d*%d ",dp[n][re[i]],re[i]);
            ans += dp[n][re[i]]*dp[n][re[i]];
        }
        //printf("\n%d\n",ans);
        if(cas) {
            cas =0;
        }else cout<<endl;
        cout<<ans<<endl;
    }
    return 0;
}