alan23273850 的刷題筆記
d757: 11195 - Another n-Queen Problem
Tags: 8-queen, bitmask, performance
出處：https://zerojudge.tw/ShowProblem?problemid=d757
提交：https://zerojudge.tw/Submissions?problemid=d757&account=allllllan123456
問題：給你許多個正整數 $N\in[4,14]$，每個正整數會對應到一個棋盤的邊長，對於每個棋盤我們都限制有些位置不能放置皇后，那請問每個棋盤分別有多少種擺放 $N$ 皇后的方法。
解法：這題如果用傳統的 DFS 試誤法應該也是會過，但是我想說既然我已經過了極致加速版的 d543，那不如就直接改那題的 code 吧！我們可以把題目輸入的每個 row 的限制點轉成一個 bitmask 稱為 full[i]，那麼限制點就是那些 full[i] 的 0-bits。第 9 行的 for loop 一開始的 ava 用 full[row]& 就能先行把限制點去除，另外第 8 行斷定擺放完畢的條件也不再是看 col 有沒有放滿，因為有限制點的緣故，只要確定每個 row 都考慮過後就能算是一種了。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n, counter;
5unsigned full[14];
6
7void dfs(unsigned row, unsigned col, unsigned diag1, unsigned diag2) {
8 if (row == n) counter++;
9 for (unsigned ava=full[row]&~(col|diag1|diag2), now=ava&-ava; // now is the current position to be placed.
10 ava; ava^=now, now=ava&-ava) // ava is short for available columns.
11 dfs(row+1, col|now, (diag1|now)<<1, (diag2|now)>>1);
12}
13
14int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
15 for (int t=1; cin >> n && n; t++) {
16 memset(full, 0, sizeof full);
17 for (int i=0; i<n; i++) {
18 char str[15]; cin >> str;
19 for (int j=0; j<n; j++) {
20 full[i] <<= 1;
21 if (str[j] == '.') full[i] |= 1;
22 }
23 }
24 counter=0, dfs(0, 0, 0, 0), cout << "Case " << t << ": " << counter << '\n';
25 }
26 return 0;
27}