c104 - 00167 - The Sultan's Successors
題目描述
題目描述了在一個 8x8 的棋盤上放置 8 個皇后，使得皇后彼此不攻擊，並找到放置方式使得皇后所在格子的數字總和最大。
解題思路
程式碼使用回溯法 (Backtracking) 產生所有可能的 8 皇后放置方案。vp 函數檢查在給定的位置放置皇后是否安全（不與其他皇后衝突）。lq 函數遞迴地嘗試在每一列放置皇后，如果找到一個有效的方案，則將其儲存在 ans 陣列中。主函數讀取棋盤上的數字，然後對於每個找到的 8 皇后放置方案，計算皇后所在格子的數字總和，並找到最大的總和。
複雜度分析
- 時間複雜度: O(8^8 * 64)。產生所有 8 皇后解的複雜度約為 O(8^8)，對於每個解，計算總和需要遍歷 8x8 的棋盤，因此是 O(64)。
- 空間複雜度: O(8 * 8 * 92)。
ans陣列儲存所有可能的 8 皇后解，大小為 8x8x92。queen陣列大小為 8x8。
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
bool ans[8][8][92],queen[8][8];
int counter=0,maxn,t[8][8],k;
bool vp(int r , int c){
for(int i=0;i<8;++i){
if(queen[i][c]&&i!=r)
return 0;
else if(queen[r][i]&&i!=c)
return 0;
else if(r+i<8&&c+i<8&&queen[r+i][c+i])
return 0;
else if(r+i<8&&c-i>=0&&queen[r+i][c-i])
return 0;
else if(r-i>=0&&c+i<8&&queen[r-i][c+i])
return 0;
else if(r-i>=0&&c-i>=0&&queen[r-i][c-i])
return 0;
}
return 1;
}
void lq(int col){
for(int j=0;j<8;++j){
queen[col][j]=vp(col,j);
if(col==7&&queen[col][j]){
for(int ii=0;ii<8;++ii)
for(int jj=0;jj<8;++jj)
ans[ii][jj][counter]=queen[ii][jj];
++counter;
queen[col][j]=0;
break;
}
else if(queen[col][j]){
lq(col+1);
queen[col][j]=0;
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
lq(0);
cin >> k;
while(k--){
for(int i=0;i<8;++i)
for(int j=0;j<8;++j)
cin >> t[i][j];
maxn=0;
for(int cc=0;cc<92;++cc){
int ansc=0;
for(int i=0;i<8;++i)
for(int j=0;j<8;++j)
if(ans[i][j][cc])
ansc+=t[i][j];
if(ansc>maxn)
maxn=ansc;
}
cout << setw(5) << maxn << "\n";
}
}