c133 - 00639 - Don't Get Rooked
題目描述
題目要求在一個 n x n 的棋盤上放置儘可能多的城堡，使得任何兩個城堡都不能互相攻擊。棋盤上可能存在牆壁，牆壁會阻擋城堡的攻擊路徑。
解題思路
這題使用深度優先搜尋 (DFS) 搭配回溯法來解決。judge 函數用於判斷在給定的位置放置城堡是否合法，即該位置是否為空，並且在其水平和垂直方向上沒有其他城堡可以攻擊到它。dfs 函數遞迴地嘗試在棋盤上放置城堡，並更新最大城堡數量。程式從棋盤的每個位置開始搜尋，如果該位置可以放置城堡，則將其標記為已佔用，遞迴地繼續搜尋，然後將其恢復到原始狀態（回溯）。
複雜度分析
- 時間複雜度: O(n^n)。在最壞的情況下，需要嘗試所有可能的城堡放置組合。
- 空間複雜度: O(n^2)。主要用於儲存棋盤狀態和遞迴呼叫堆疊。
程式碼
#include <iostream>
using namespace std;
int n,ans;
char a[5][5];
bool judge(int x,int y){
if(a[x][y]=='X'){
return 0;
}
for(int i=1;i<n;++i){
if(i+x>=n||a[i+x][y]=='X')break;
if(a[i+x][y]=='O')return 0;
}
for(int i=1;i<n;++i){
if(x-i<0||a[x-i][y]=='X')break;
if(a[x-i][y]=='O')return 0;
}
for(int i=1;i<n;++i){
if(i+y>=n||a[x][y+i]=='X')break;
if(a[x][y+i]=='O')return 0;
}
for(int i=1;i<n;++i){
if(y-i<0||a[x][y-i]=='X')break;
if(a[x][y-i]=='O')return 0;
}
return 1;
}
void dfs(int x,int y,int v){
ans=max(ans,v);
for(int i=x;i<n;++i){
for(int j=(x==i?y+1:0);j<n;++j){
if(judge(i,j)){
a[i][j]='O';
dfs(i,j,v+1);
a[i][j]='.';
}
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(n==0)break;
ans=0;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cin >> a[i][j];
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(judge(i,j)){
a[i][j]='O';
dfs(i,j,1);
a[i][j]='.';
}
}
}
cout << ans << "\n";
}
}