Koios1143的筆記

UVa 11195

發表於 分類於

UVa 11195

題目

http://domen111.github.io/UVa-Easy-Viewer/?11195

經典 N 皇后問題

給定一個 $N \times N$ 的西洋棋棋盤，棋盤上可能有障礙物，障礙物可以抵擋攻擊

現在要在這個棋盤上放上 $N$ 個皇后，並且彼此都不會攻擊到對方，請問有多少種解法

想法

想法跟過去 DFS 解 8 皇后問題是一樣的

對於每個可以放皇后的格子嘗試去放，然後看看能不能放滿整個盤面

不同的是，我們不需要每次都往三個方向(左斜/右斜/直)掃過去檢查，而是改用位元運算的想法

Note

不考慮橫向是因為在 DFS 的過程當中我們就只會取每一列中其中一個下去枚舉，所以橫向必定不會互相攻擊

以左斜向來看，我們可以用一個數字 $m$ 相對應的 bit 去記錄該點是否會被攻擊到

如果可以被攻擊的話，那麼枚舉下一列的時候會被攻擊到的點就會是 $m$ 全部 bit 左移後的位置

Note

舉例來說，如果當前是 $4 \times 4$ 的棋盤，並且在第一列可以被左斜向攻擊到的有第 $3$ 行

當前 $m$ 以二進位表示為 $0010$

在枚舉到第二列的時候可以攻擊的點會左移，也就是變成 $0100$

類似地，右斜向則是每次都會向右移一個 bit

至於直向也一樣用一個數字相對應的 bit 紀錄可否被攻擊，只是枚舉下一列時並不需要改變

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//By Koios1143
#include<iostream>
using namespace std;
int n, ans, Case=1;
char arr[20][20];

// depth 表示當前枚舉的列數
void DFS(int depth, int Lslash, int Rslash, int straight){
	if(depth == n){
		ans++;
		return;
	}
	// 對於每一行去判斷
	// 1. 該點是否沒障礙物
	// 2. 左斜向攻擊是否會攻擊到
	// 3. 右斜向攻擊是否會攻擊到
	// 4. 直向攻擊是否會攻擊到
	for(int i=0 ; i<n ; i++){
		if(arr[depth][i] == '.' && ((Lslash & (1<<i)) == 0) && ((Rslash & (1<<i)) == 0) && ((straight & (1<<i)) == 0)){
			// 記得先把自己加進去，然後再左移右移
			DFS(depth+1, (Lslash | (1<<i))<<1, (Rslash | (1<<i))>>1, (straight | (1<<i)));
		}
	}
}

int main(){
	while(cin>>n && n){
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<n ; j++){
				cin>>arr[i][j];
			}
		}
		ans=0;
		DFS(0, 0, 0, 0);
		cout<<"Case "<<Case++<<": "<<ans<<"\n";
	}

	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n^2)$

每筆測資 DFS 時間複雜度為 $O(n^n)$

每筆測資總時間複雜度為 $O(n^n)$