跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:19:20

    【本题解由站长编写】

    按行搜索:每一行先放一个黑皇后、再放一个白皇后。同色皇后之间不能同列、同对角线(行号天然不同);黑与白之间唯一的约束是不能落在同一格。两者都只能放到 1 格上。逐行递归,放满 n 行计数一次,n≤8 直接深搜。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int n, g[10][10], b[10], w[10];
    long long ans;
    bool ok(int *col, int r, int c) {
        for (int i = 0; i < r; i++) if (col[i] == c || abs(col[i] - c) == r - i) return false;
        return true;
    }
    void dfs(int r) {
        if (r == n) { ans++; return; }
        for (int bc = 0; bc < n; bc++) {
            if (!g[r][bc] || !ok(b, r, bc)) continue;
            b[r] = bc;
            for (int wc = 0; wc < n; wc++) {
                if (wc == bc || !g[r][wc] || !ok(w, r, wc)) continue;
                w[r] = wc;
                dfs(r + 1);
            }
        }
    }
    int main() {
        cin >> n;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> g[i][j];
        dfs(0);
        cout << ans << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4072
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    0
    上传者