搭積木

題目

搭積木

思路

? 首先理一下題目，需要注意以下:

1. 從給定的圖自底向上擺積木， 不擺是一種方案，并且m個(gè)積木已經(jīng)作為地基
2. 擺放的時(shí)候保證下方有積木，并且連續(xù)擺放，不能有縫隙
3. ‘X’表示該點(diǎn)不能擺放

? 設(shè)\(f[i][l][r]\)表示前\(i - 1\)層已經(jīng)擺放好，第\(i\)層在\([l, r]\)這段區(qū)間內(nèi)連續(xù)擺放小方塊的方案數(shù)量。

? 那么有，\(f[i][l][r] = \sum \limits_{l \le x\le y\le r}f[i][x][y]\)。

? 為什么那， 畫(huà)個(gè)圖：

?

? 考慮上面的圖， \(f[1][l][r]\) 一定是從\(f[2][x][y]\)， 且\(x, y\)一定是在\([l, r]\)內(nèi)轉(zhuǎn)移的， 因?yàn)轭}目的要求保證了金字塔形狀， 我們倒著推，一定是從更小的區(qū)域轉(zhuǎn)移過(guò)來(lái)的。

? 由于方程轉(zhuǎn)移需要還沒(méi)有求出的狀態(tài)，我們可以用記憶化搜索來(lái)推出所有的狀態(tài)。

#include <bits/stdc++.h>

using i64 = long long;

const int N = 110, mod = 1e9 + 7;

int n, m;

char s[N][N];

int f[N][N][N];

/*
	f[i][l][r] 表示已經(jīng)擺好i - 1 ~ n, 在區(qū)間[l, r] 內(nèi)連續(xù)擺放一段積木的方案數(shù)
*/

int dfs(int dep, int l, int r) {
	if (dep == 0) return 1;
	if (f[dep][l][r] != -1) return f[dep][l][r];

	i64 ans = 1;

	for (int i = l; i <= r; i ++) {
		if (s[dep][i] == '.') {
			for (int j = i; j <= r; j ++) {
				// 若區(qū)間內(nèi)有'X' break
				if (s[dep][j] == 'X') {
					break;
				}
				ans = (ans + dfs(dep - 1, i, j)) % mod;
			}	
		}	
	}
	f[dep][l][r] = ans;
	return f[dep][l][r];
}

int main() {
	std::cin >> n >> m;

	for (int i = 1; i <= n; i ++) {
		std::cin >> s[i] + 1;	
	}

	memset(f, -1, sizeof f);

	dfs(n, 1, m);

	std::cout << f[n][1][m];
}