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
| /*
*File: 2411.cpp
*Date : 2015-05-19 23:43:40
*/
#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[12][1<<11];
vector <int > v[12];
bool inque[12][1<<11];
int n,m;
int res;
int now;
void dfs(int l,int st)
{
if(l>m) return ;
if(l==m)
{
dp[now+1][st] += dp[now][res];
if(!inque[now+1][st])
{
inque[now+1][st] = 1;
v[now+1].push_back(st);
}
return ;
}
if((res&(1<<l))==0&&(res&(1<<(l+1)))==0)
{
dfs(l+2,st);
}
if((res&(1<<l)))
{
dfs(l+1,st);
}
else {
dfs(l+1,st|(1<<l));
}
}
int main()
{
while(~scanf("%d%d",&n,&m)&&n*m)
{
memset(dp,0,sizeof dp);
memset(inque,0,sizeof inque);
dp[0][0] = 1;
for(int i =0;i<=n;i++)
v[i].clear();
v[0].push_back(0);
for(int i = 1;i<=n;i++)
{
for(int j = 0 ;j<v[i-1].size();j++)
{
res = v[i-1][j];
now = i-1;
dfs(0,0);
// printf("%d %d %d\n",i,j,dp[i][j]);
}
}
printf("%lld\n",dp[n][0]);
}
return 0;
}
|