这算是八皇后问题的变种了,普通的组合数学已经很难一下子将他求出来了,除此之外,我们用纯模拟来处理该题。
给定是一个N*N的矩阵,要求在这个图中放置K个点,这些点不能够相邻(包括上下左右以及对角线上的区域),用模拟如何来过这一题呢,那就是要推出动态递归方程,F[i][s][k] 代表第i行处于第s个状态且到目前行共下了k个棋子的总方案数,c[s]代表针对s这个状态有多少个1,有动态方程:F[i][s][k] = sum{ F[i-1][s'][k-c[s]],其中 s 与 s' 为不冲突的方案数 } 该方程的含义为 F[i][s][k] 中剩余的棋子数 k-c[s] 在上一行截止时所走的总方案。代码如下:
#include#include #include #include #define MAXN 150 using namespace std; int N, K, M, s[MAXN], c[MAXN]; long long f[11][MAXN][MAXN]; void dfs(int l, int state, int total) { if (l == N) { s[M] = state; c[M++] = total; return; // 递归就此结束 } dfs(l+1, state<<1, total); // 不管左边相邻的列是否放置,该位不放置总是行的 if (!(state&1)) dfs(l+1, state<<1|1, total+1); } bool judge(int s1, int s2) { if (s[s1] & s[s2]) return false; if (s[s1]<<1 & s[s2]) return false; if (s[s2]<<1 & s[s1]) return false; return true; } void dp(int l, int state, int k) { f[l][state][k] = 0; for (int i = 0; i < M; ++i) { if (k >= c[state] && judge(i, state)) { if (f[l-1][i][k-c[state]] == -1) dp(l-1, i, k-c[state]); f[l][state][k] += f[l-1][i][k-c[state]]; } } } int main() { long long ans = 0; M = 0; // M 表示状态的数量 memset(f, 0xff, sizeof (f)); scanf("%d %d", &N, &K); dfs(0, 0, 0); memset(f[0], 0, sizeof (f[0])); f[0][0][0] = 1; // 中间的0代表第1种状态 for (int i = 0; i < M; ++i) { if (f[N][i][K] == -1) { dp(N, i, K); } ans += f[N][i][K]; } cout << ans; return 0; }