UVa 167

題目

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

在一個 $8 \times 8$ 的西洋棋棋盤上要放上 $8$ 個皇后，並且所有皇后之間彼此不能在對方的攻擊範圍內，也就是經典的 $8$ 皇后問題

現在在棋盤上的每個格子都有一個數字，求所有符合 $8$ 皇后的情況下，所有皇后所在的格子數字總和最大是多少

想法

因為棋盤大小固定只有 $8 \times 8$，可以考慮用比較暴力的方式去做

枚舉每一橫排的皇后可以存在的位置，直到所有橫排都枚舉完後記錄當前的數字總和並記錄下最大的情況

Code

//By Koios1143
#include<iostream>
#include<iomanip>
using namespace std;
int arr[8][8], path_x[8], path_y[8], k, ans;
void dfs(int depth){
	if(depth == 8){
		int tot=0;
		// 計算當前數字總和
		for(int i=0 ; i<8 ; i++){
			tot += arr[path_x[i]][path_y[i]];
		}
		// 找出最大值
		ans=max(ans, tot);
		return;
	}
	// 對於橫排的 8 個位置枚舉
	for(int i=0 ; i<8 ; i++){
		bool cango = true;
		// 檢查 depth 排以前的皇后與現在的位置是否衝突
		for(int j=0 ; j<depth ; j++){
			// 檢查是否在同一列上
			if(path_y[j] == i){
				cango=false;
				break;
			}
			// 檢查是否在同一斜線上
			if(abs(path_x[j]-depth) == abs(path_y[j]-i)){
				cango=false;
				break;
			}
		}
		if(cango){
			path_x[depth] = depth;
			path_y[depth] = i;
			dfs(depth+1);
		}
	}
}
int main(){
	cin>>k;
	while(k--){
		ans=0;
		for(int i=0 ; i<8 ; i++){
			for(int j=0 ; j<8 ; j++){
				cin>>arr[i][j];
			}
		}
		dfs(0);
		// 輸出格式須符合總長度為 5，不足則以空格補齊
		cout<<setw(5)<<ans<<"\n";
	}
	return 0;
}

時間複雜度分析

令 $n = 8$

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

DFS 每層最多有 $8$ 種選擇，總共有 $8$ 層

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

總時間複雜度為 $O(kn^{n+2})$