a597_2 - Island Counting
題目描述
題目要求計算一個由 'J' 表示的矩陣中，相連 'J' 形成的島嶼的數量以及其中最大島嶼的大小。相連的 'J' 定義為上下左右四個方向相鄰的 'J'。如果矩陣中 'J' 的數量少於矩陣的最小邊長，則輸出 "1 to"，其中 to 是 'J' 的數量。否則，輸出島嶼的數量和最大島嶼的大小。
解題思路
這題的核心是使用深度優先搜尋 (DFS) 來尋找相連的 'J'，並計算每個島嶼的大小。程式首先讀取矩陣的尺寸和內容，然後遍歷矩陣。如果遇到 'J'，則啟動 DFS，標記該 'J' 為已訪問，並遞迴地探索其相鄰的 'J'。在 DFS 過程中，統計島嶼的大小。最後，計算島嶼的總數和最大島嶼的大小，並根據題目要求輸出結果。如果 'J' 的數量少於矩陣的最小邊長，則直接輸出 "1 to"。
複雜度分析
- 時間複雜度: O(m*n)，其中 m 和 n 分別是矩陣的行數和列數。因為每個單元格最多被訪問一次。
- 空間複雜度: O(mn)，主要來自於
mp矩陣和 DFS 的遞迴堆疊空間。在最壞情況下，整個矩陣都是 'J'，DFS 的深度可能達到 mn。
程式碼
#include <iostream>
using namespace std;
int m,n,tmp,ans,total,to;
bool mp[501][501];
char c;
void dfs(int x,int y){
if(x<0||y<0||x>=m||y>=n||mp[x][y]==0)return;
++tmp;
mp[x][y]=0;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> m >> n){
ans=tmp=total=to=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
cin >> c;
if(c=='J'){
mp[i][j]=1;
++to;
}
else
mp[i][j]=0;
}
}
if(m*n-to<min(m,n)){
cout << "1 " << to << "\n";
}
else{
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(mp[i][j]){
tmp=0;
++total;
dfs(i,j);
ans=max(tmp,ans);
}
}
}
cout << total << " " << ans << "\n";
}
}
}