b510 - M 皇后 N 城堡
題目描述
題目要求計算在一個 (M+N) x (M+N) 的棋盤上放置 M 個皇后和 N 個城堡的合法方案數。皇后可以沿著水平、垂直和對角線移動，而城堡只能沿著水平和垂直方向移動。所有棋子都不能互相攻擊。
解題思路
此題使用回溯法 (Backtracking) 求解。首先，嘗試放置 M 個皇后，然後在放置皇后後，嘗試放置 N 個城堡。在放置每個棋子時，檢查該位置是否安全，即該位置是否不在任何其他棋子的攻擊範圍內。如果安全，則放置該棋子並繼續放置下一個棋子。如果所有棋子都已放置，則增加方案數。放置完所有可能的方案後，返回總方案數。
c 函數用於檢查在給定的位置放置棋子是否安全。它檢查水平、垂直和對角線方向上是否有其他棋子。put 函數用於放置皇后，put2 函數用於放置城堡。us 陣列用於記錄每一行是否已經放置了皇后。
複雜度分析
- 時間複雜度: O( (M+N)! )，在最壞情況下，需要嘗試所有可能的棋子放置組合。
- 空間複雜度: O( (M+N)^2 )，主要用於儲存棋盤狀態
a和us陣列。
程式碼
#include <iostream>
using namespace std;
int a[11][11],m,n,mn,ans,us[11];
inline bool c(int x,int y,int t){
for(int i=0;i<mn;++i)
if(a[x][i]||a[i][y])return 0;
if(t==1){
for(int i=0;i<mn&&i+x<mn&&i+y<mn;++i)
if(a[x+i][y+i])return 0;
for(int i=0;i<mn&&x-i>=0&&y-i>=0;++i)
if(a[x-i][y-i])return 0;
for(int i=0;i<mn&&x-i>=0&&y+i<mn;++i)
if(a[x-i][y+i])return 0;
for(int i=0;i<mn&&x+i<mn&&y-i>=0;++i)
if(a[x+i][y-i])return 0;
}
else{
for(int i=0;i<mn&&i+x<mn&&i+y<mn;++i)
if(a[x+i][y+i]==1)return 0;
for(int i=0;i<mn&&x-i>=0&&y-i>=0;++i)
if(a[x-i][y-i]==1)return 0;
for(int i=0;i<mn&&x-i>=0&&y+i<mn;++i)
if(a[x-i][y+i]==1)return 0;
for(int i=0;i<mn&&x+i<mn&&y-i>=0;++i)
if(a[x+i][y-i]==1)return 0;
}
return 1;
}
inline void put2(int y,int s){
if(s==n){
++ans;
return;
}
for(int i=0;i<mn;++i){
if(!us[i])
for(int j=y;j<mn;++j)
if(!a[i][j]&&c(i,j,2)){
a[i][j]=2;
us[i]=1;
put2(j,s+1);
us[i]=0;
a[i][j]=0;
}
}
}
void put(int y,int s){
if(s==m){
for(int i=0;i<mn;++i){
if(!us[i])
for(int j=0;j<mn;++j)
if(!a[i][j]&&c(i,j,2)){
us[i]=1;
a[i][j]=2;
put2(j,1);
a[i][j]=0;
us[i]=0;
}
}
return;
}
for(int i=0;i<mn;++i){
if(!us[i])
for(int j=y;j<mn;++j)
if(!a[i][j]&&c(i,j,1)){
a[i][j]=1;
us[i]=1;
put(j,s+1);
us[i]=0;
a[i][j]=0;
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> m >> n){
ans=0;
mn=m+n;
for(int i=0;i<mn;++i){
us[i]=0;
for(int j=0;j<mn;++j)
a[i][j]=0;
}
for(int i=0;i<mn;++i)
for(int j=0;j<mn;++j){
a[i][j]=1;
us[i]=1;
put(j,1);
us[i]=0;
a[i][j]=0;
}
cout << ans << "\n";
}
}