UVA 861 N*N棋盘放置K个Bishop的回溯转DP解法求助

回溯方案性能问题分析 #

你的回溯解法本质是穷举所有可能的放置位置，时间复杂度为指数级，当n≥8、k≥6时运算量会暴涨，无法满足时效要求。

DP解法核心思路 #

首先利用Bishop的攻击特性简化问题：

• Bishop只能攻击和自己同色的棋盘格（棋盘黑白染色后，斜向移动永远不会改变格子颜色），因此黑格和白格的放置完全独立，总方案数等于所有「黑格放i个Bishop的方案数 × 白格放k-i个Bishop的方案数」的累加和，i的取值范围是max(0, k-白格最大可放数)到min(k, 黑格最大可放数)。
• 将棋盘旋转45度，原来的斜向攻击线就变成了横向和纵向的线，此时在同色块上放置互不攻击的Bishop，等价于在新的矩阵中放置互不攻击的车（不能同行同列），这个场景的计数可以用DP高效实现。

DP状态定义与转移 #

我们针对单种颜色的格子定义DP：

• dp[i][j]：表示前i条斜行共放置j个互不攻击的Bishop的方案数
• 转移方程：
  • 第i条斜行不放Bishop：dp[i][j] += dp[i-1][j]
  • 第i条斜行放1个Bishop：dp[i][j] += dp[i-1][j-1] * (cnt[i] - (j-1))，其中cnt[i]是第i条斜行的格子总数，j-1是前面已经放置的Bishop占用的列数，剩下的位置都可以放。

可运行的DP实现代码 #

#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;
// 最多支持n=15，k最大28，可根据需求调整上限
ll dp1[40][40], dp2[40][40]; // dp1存黑格方案，dp2存白格方案
int cnt1[40], cnt2[40]; // 分别存黑白格每条斜行的格子数

void init(int n) {
    memset(cnt1, 0, sizeof cnt1);
    memset(cnt2, 0, sizeof cnt2);
    // 统计黑白斜行的格子数
    for(int i=1; i<=n-1; i+=2) cnt1[i] = i+1;
    for(int i=0; i<=n-1; i+=2) cnt2[i] = i+1;
    int idx = n % 2 == 1 ? n : n-1;
    for(int i = n-2, t = idx - 2; i >= 0; i -= 2, t -= 2) {
        cnt1[idx++] = t;
    }
    idx = n % 2 == 0 ? n : n-1;
    for(int i = n-2, t = idx - 2; i >= 0; i -= 2, t -= 2) {
        cnt2[idx++] = t;
    }
    // 预处理dp1
    memset(dp1, 0, sizeof dp1);
    dp1[0][0] = 1;
    int len1 = 2*n -1;
    for(int i=1; i<=len1; i++) {
        dp1[i][0] = 1;
        for(int j=1; j<=i; j++) {
            dp1[i][j] = dp1[i-1][j] + dp1[i-1][j-1] * (cnt1[i-1] - (j-1));
        }
    }
    // 预处理dp2
    memset(dp2, 0, sizeof dp2);
    dp2[0][0] = 1;
    int len2 = 2*n -1;
    for(int i=1; i<=len2; i++) {
        dp2[i][0] = 1;
        for(int j=1; j<=i; j++) {
            dp2[i][j] = dp2[i-1][j] + dp2[i-1][j-1] * (cnt2[i-1] - (j-1));
        }
    }
}

ll solve(int n, int k) {
    if(k > 2*n -2) return 0; // n*n棋盘最多放2n-2个互不攻击的Bishop
    init(n);
    ll res = 0;
    for(int i=0; i<=k; i++) {
        res += dp1[2*n-1][i] * dp2[2*n-1][k - i];
    }
    return res;
}

int main() {
    int n, k;
    while(cin >> n >> k && (n || k)) {
        cout << solve(n, k) << endl;
    }
    return 0;
}

时间复杂度说明 #

预处理两个DP表的时间复杂度都是O(n²)，单次查询的复杂度是O(k)，哪怕n到15也能秒出结果，远优于回溯解法。

内容的提问来源于stack exchange，提问作者kbh