f493 - 水窪問題
題目描述
題目給定一個 N x M 的地圖，其中 'W' 代表水窪，'#' 代表陸地。要求計算最大水窪的大小、最小水窪的大小以及水窪的總數。水窪定義為連續的 'W' 區域。
解題思路
使用深度優先搜尋 (DFS) 來遍歷地圖，找出所有水窪。對於每個未訪問的水窪 ('W')，啟動一次 DFS，並計算該水窪的大小。在 DFS 過程中，將訪問過的 'W' 標記為 '#'，以避免重複計算。同時記錄遇到的最大和最小水窪大小，以及水窪的總數。
複雜度分析
- 時間複雜度: O(M * N)，其中 M 和 N 分別是地圖的行數和列數。因為 DFS 最多會遍歷地圖上的每個格子一次。
- 空間複雜度: O(M * N)，主要來自於遞迴呼叫堆疊的空間，在最壞情況下，整個地圖都是水窪，DFS 的深度可能達到 M * N。
程式碼
#include <iostream>
using namespace std;
char a[1001][1001];
int m,n,ma,mi=1000001,t,tmp;
inline void dfs(int x,int y){
if(x>=m||y>=n||x<0||y<0||a[x][y]!='W')return;
a[x][y]='#';
++tmp;
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);
cin >> m >> n;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
cin >> a[i][j];
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(a[i][j]=='W'){
++t;
tmp=0;
dfs(i,j);
ma=max(ma,tmp);
mi=min(mi,tmp);
}
}
}
if(ma==0)
mi=0;
cout << ma << " " << mi << " " << t ;
}