papamelon 321. 铺砖问题（挑战程序设计竞赛）

地址 https://www.papamelon.com/problem/321

解答
首先是尝试把该问题转化成蒙德里安的梦想那道题，但是由于复杂度是2^n*2n,当n为15的时候就超时了。
后面改成了记忆化搜索.可以去掉一些不可能达到的状态搜索,OK了。
大概这就是记忆化搜索相对直接递推DP公式的优势吧

int dp[N][M]表示第N行状态为M的摆放完全的摆放方案数字
M转化为01二进制状态 代表 0为横放一块积木。1代表竖放一块积木.

两行没有冲突的防止方案就是
1 两行都是横放 上行为00 下一行也是00

2 上一行有竖放 且下一行没有竖放
上行为1 下行为0
也就是 (state1 & state2) ==0

两行没有冲突的合并后 连续的0必须是偶数 否则无法横放1*2的方块
也就是(state1 | state2)的连续0个数必须是偶数

符合这两个条件才能说明两行状态可以转化。
但是这里还有个特例是表示不能放置砖块的x,
无论是检测两行合并是否可以兼容竖放方块还是检测合并后是否有连续的偶数的0 放置，将该位置其当作1 看待

#include 
#include 

using namespace std;

const int N = 16;
const int M = 1 << N;

/*
3 3 10000
...
.x.
...
*/


int dp[N][M];
char mm[N][N];
int n, m, MOD;
int st[M];
int xNum[N];

bool CheckX(int k, int idx) {
	if ((k & xNum[idx]) != 0) {
		return false;
	}
	return true;
}

int FillX(int j, int idx) {
	j |= xNum[idx];
	return j;
}


//输入状态和所在行
int GetTotal(int state, int line) {
	int& ret = dp[line][state];
	if ( ret >= 0) {
		return ret;
	}

	ret = 0;
	int stateFill = FillX(state,line);
	for (int i = 0; i < 1 << m; i++) {
		//如果该状态符合该行的X 并且可以与当前行不冲突
		//也就是可以从上一行的i状态转移过来 加上他的可操作数
		if ( true == CheckX(i, line - 1) && (stateFill&i) == 0 && 1== st[stateFill | i]) {
			//if(line -1 == 2)
				//cout << "line = " << line-1  <<" state = " << i << endl;
			ret += GetTotal(i,line-1);
			ret %= MOD;
		}
	}

	return ret;
}


void initState() {
	for (int i = 0; i < 1 << m; i++) {
		int isvalid = 1; int cnt = 0;
		for (int j = 0; j < m; j++) {
			if ((i >> j) & 1) {
				if (cnt & 1) { isvalid = 0; break; }
				cnt = 0;
			}
			else { cnt++; }
		}
		if (cnt & 1) { isvalid = 0; }
		if (1 == isvalid) { st[i] = 1; }
	}
}

//初始化dp数组
void initDp() {
	memset(dp, -1, sizeof dp);
	for (int i = 1; i < M; i++) {
		dp[0][i] = 0;
	}
	dp[0][0] = 1;
}

void solve() {
	//初始化dp
	initDp();
	//计算所有合乎规则的状态
	initState();

	int ans = GetTotal(0,n);
	cout << ans << endl;

	return;
}

int main()
{
	cin >> n >> m >> MOD;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mm[i][j];
			if (mm[i][j] == 'x')
				xNum[i] += 1 << (m - 1 - j);
		}
	}

	solve();

	return 0;
}

我的视频题解空间