f822 - 紅林愛下棋
題目描述
題目描述一個 9x9 的圍棋棋盤，要求判斷黑棋 (B) 和白棋 (W) 誰的地盤更大。如果棋盤存在未完成的區域，即同時被黑白棋圍繞，則輸出 "Wrong"。否則，輸出獲勝者、雙方地盤比分以及最終棋盤狀態。
解題思路
本題的核心是遍歷棋盤，尋找未標記的空地，並使用深度優先搜尋 (DFS) 將其標記為黑棋或白棋。DFS 的起始點是未標記的空地，它會遞迴地向四個方向擴展，直到遇到棋盤邊界、已標記的棋子或同時存在黑白棋子。如果 DFS 過程中遇到同時存在黑白棋子的情況，則判定棋盤不合法，輸出 "Wrong"。
程式首先讀取棋盤的初始狀態。然後，它遍歷棋盤，尋找未標記的空地。對於每個未標記的空地，它呼叫 DFS 函數，將相鄰的空地標記為黑棋或白棋。在 DFS 過程中，如果遇到同時存在黑白棋子的情況，則將 type 設為 -1，表示棋盤不合法。
DFS 函數的邏輯如下：
- 如果超出棋盤邊界、
type為 -1 或遇到已標記的棋子，則返回。 - 如果遇到白棋，則將
type設為 2。 - 如果遇到黑棋，則將
type設為 1。 - 如果遇到空地，則將其標記為 '*'，並遞迴地呼叫 DFS 函數，向四個方向擴展。
在 DFS 完成後，程式計算黑棋和白棋的地盤數量，並輸出結果。
複雜度分析
- 時間複雜度: O(N*M)，其中 N 和 M 分別是棋盤的行數和列數。因為程式需要遍歷整個棋盤，並且 DFS 最多會訪問每個格子一次。在本題中，N=M=9，所以時間複雜度為 O(81)。
- 空間複雜度: O(NM)，主要來自於棋盤
ans的儲存空間。此外，DFS 的遞迴深度可能達到 NM，因此遞迴堆疊的空間複雜度也為 O(N*M)。在本題中，空間複雜度為 O(81)。
程式碼
#include <iostream>
using namespace std;
int a,b,type;
char ans[10][10];
void dfs(int x,int y){
if(x<0||y<0||x>=9||y>=9||type==-1||ans[x][y]=='*')return;
if((type==1&&ans[x][y]=='W')||(type==2&&ans[x][y]=='B')){
type=-1;
return;
}
if(ans[x][y]=='W'){
type=2;
return;
}
else if(ans[x][y]=='B'){
type=1;
return;
}
else{
ans[x][y]='*';
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
}
}
int main(){
for(int i=0;i<9;++i)
for(int j=0;j<9;++j)
cin >> ans[i][j];
for(int i=0;i<9&&type!=-1;++i){
for(int j=0;j<9&&type!=-1;++j){
if(ans[i][j]=='B')
++a;
else if(ans[i][j]=='W')
++b;
else{
type=0;
dfs(i,j);
if(type==-1)break;
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
if(ans[i][j]=='*'){
if(type==1)
ans[i][j]='B';
else
ans[i][j]='W';
}
}
}
if(type==1)
++a;
else
++b;
}
}
}
if(type==-1)
cout << "Wrong\n";
else{
if(a>b)
cout << "Black wins!!\n";
else
cout << "White wins!!\n";
cout << a << ":" << b << "\n";
for(int i=0;i<9;++i){
for(int j=0;j<9;++j)
cout << ans[i][j];
cout << "\n";
}
}
}