AcWing 291. java同学
原题链接
中等
作者:
季之秋
,
2021-02-19 15:58:17
,
所有人可见
,
阅读 251
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=12,M=1<<N;//N是行,M是二进制状态
boolean st[]=new boolean[M];//这个状态的有效性
while(true){
int n=sc.nextInt();
int m=sc.nextInt();
if(n==0&m==0) break;
for(int i=0;i<(1<<n);i++){//每个状态预处理有效性
st[i]=true;
int cnt=0;
for(int j=0;j<n;j++){//如果0位是连续奇数就无效
if(((i>>j)&1)==1) {
if((cnt&1)==1) st[i]=false;
cnt=0;
}
else cnt++;
}
if(cnt%2==1) st[i]=false;//最后一位是0的情况也要判断
}
long f[][]=new long[N][M];//初始化防止沉淀
f[0][0]=1;//第一列只有 00000000 的这一种方案 第二列可能 00000000 或 11111111 ……
for(int i=1;i<=m;i++){ //遍历列,m结尾才能计算到m-1列的方案数
for(int j=0;j<(1<<n);j++){ //i的状态
for(int k=0;k<(1<<n);k++){ //i-1的状态 如果写成一层循环那i和i-1状态就一直一样了
if((j&k)==0&&st[j|k]){ //两个状态任一位上不能都是1;
//两个状态都没有放木块的层数不能是奇数,否则放竖的长方形就会有空余位置
f[i][j]+=f[i-1][k];
//i状态等于i-1所有状态的和:f[i][j]不变,f[i-1][k]在变也会是一种方案
}
}
}
}
System.out.println(f[m][0]);
//因为是放满的,所有不会有木头捅出来到m列,而且会一直累加方案状态,所有状态都累加到了m层
}
}
}