棋盘问题 题解

这题不是状压DP板子题吗（
注意到棋盘大小很小，考虑状压DP。
$dp[i][j][k]$ 为前 $i$ 行摆了 $k$ 枚棋子，棋子摆放状态为 $j$ 的情况。如果某个位置是 #，则所有前面没有摆放过这个列的状态都可以转移过来。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
string a[9];
int dp[9][1 << 8][9];
bool solve(){
	int n, m;
	cin >> n >> m;
	if(n == -1) return 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	dp[0][0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (1 << n); j++){
			for(int k = 0; k <= m; k++){
				dp[i][j][k] = dp[i - 1][j][k];
			}
			for(int k = 0; k < n; k++){
				if(a[i][k] != '#' || (~j >> k & 1)) continue;
				for(int l = 1; l <= m; l++){
					dp[i][j][l] += dp[i - 1][j ^ 1 << k][l - 1];
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < (1 << n); i++){
		ans += dp[n][i][m];
	}
	cout << ans << '\n';
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (1 << n); j++){
			for(int k = 0; k <= m; k++){
				dp[i][j][k] = 0;
			}
		}
	}
	return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	while(solve());

	return 0;
}

时间复杂度：$O(Tmn2^n)$，优于一般深搜做法 $O(Tnn!)$ 的时间复杂度。