1 条题解
-
0
【本题解由站长编写】
按行搜索:每一行先放一个黑皇后、再放一个白皇后。同色皇后之间不能同列、同对角线(行号天然不同);黑与白之间唯一的约束是不能落在同一格。两者都只能放到 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
- 上传者