对于棋盘上每个点，都有几种可能，1.不放 2.横放的前一个 3.横放的后一个 4.竖放的上一个 5.竖放的下一个
由于题目要求每个格子都被填满，所以可能1不存在
然后，我们可以考虑用1表示这个格子被放上了2/3/5这几种可能，然后通过二级制压缩状态
对于每一行都有一个数值来表示当前行的状态 now 以及上一行的状态 pre
我们可以通过dfs将所有的可能的两行之间的状态转移预处理出来
再填写第d列的时候 有这样几种可能
1.当前位置为可能2，那么就可以把下一个一起处理了，这时候要求上一行的两个位置也都为1
2.当前位置为可能4，这样要求上一行的d列的位置为1
3.当前位置可能为5，这样要求上一行的d列位置为0
然后再进行dp统计结果即可
代码
我要评论
#include<bits/stdc++.h>
using namespace std;
int n,m,ca;
int state[200005][2];
long long dp[13][3005];
void dfs(int d,int now,int pre)
{
if(d>m) return;
if(d==m)
{
state[ca][0]=pre;
state[ca++][1]=now;
return;
}
dfs(d+1,(now<<1)|1,pre<<1);
dfs(d+1,now<<1,(pre<<1)|1);
dfs(d+2,(now<<2)|3,(pre<<2)|3);
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
while(scanf("%d%d",&n,&m) && n)
{
//if(n<m) swap(n,m);
ca=0;
dfs(0,0,0);
memset(dp,0,sizeof(dp));
dp[0][(1<<m)-1]=1;
for(int i=0;i<n;i++)
for(int j=0;j<ca;j++)
dp[i+1][state[j][1]]+=dp[i][state[j][0]];
printf("%lld\n",dp[n][(1<<m)-1]);
}
return 0;
}
本文地址：https://blog.csdn.net/andyc_03/article/details/107609464
如对本文有疑问， 点击进行留言回复！！
网友评论