c252 - 非洲內戰
題目描述
題目描述了一個非洲國家被劃分為多個派系，每個派系由一個數字代表。相鄰的相同派系可以組成一個政權。如果政權的數量大於最大派系的數量，則國家陷入混亂（輸出 "choas"），否則國家受到掌控（輸出 "peace"）。
解題思路
本題可以使用深度優先搜尋 (DFS) 來找出每個政權的大小。首先，遍歷整個地圖，如果遇到未訪問的派系，則使用 DFS 遍歷所有與該派系相鄰且相同的區域，並計算該政權的大小。記錄所有政權的大小，以及不同派系的數量。最後，比較政權的數量和最大派系的數量，以確定國家是處於 "peace" 還是 "choas" 狀態。
複雜度分析
- 時間複雜度: O(M * N)，其中 M 和 N 分別是地圖的行數和列數。因為每個格子最多被訪問一次。
- 空間複雜度: O(M * N)，主要用於
has陣列來記錄訪問過的格子，以及 DFS 的遞迴堆疊空間。在最壞情況下，整個地圖都是一個連通的政權，DFS 的深度可能達到 M * N。
程式碼
#include <iostream>
using namespace std;
int a[105][105],n,m,ct,ma,tmp;
char c;
bool has[105][105];
void dfs(int x,int y,int v){
if(x>=n||y>=m||x<0||y<0||has[x][y]||a[x][y]!=v)return;
has[x][y]=1;
++tmp;
for(int i=-1;i<=1;++i)
for(int j=-1;j<=1;++j)
dfs(x+i,y+j,v);
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
while(cin >> n >> m){
if(n==0&&m==0)return 0;
ct=ma=0;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
cin >> c;
a[i][j]=c-'0';
has[i][j]=0;
}
}
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(!has[i][j]&&a[i][j]){
tmp=0;
dfs(i,j,a[i][j]);
ma=max(ma,tmp);
++ct;
}
if(ct>ma){
cout << "choas\n";
}
else{
cout << "peace\n";
}
}
}