itdef

地址 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 <iostream>
#include <memory.h>

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;
}

我的視頻題解空間