e676 - 00469 - Wetlands of Florida
題目描述
題目描述了佛羅里達州的一塊土地，被劃分為一個網格，網格中的每個單元格可以是陸地 ('L') 或水域 ('W')。目標是對於給定的網格單元格座標，計算該單元格所屬的水域的面積。水域的面積定義為相鄰的水域單元格的數量（上下左右對角線都算相鄰）。
解題思路
此題可以使用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 來解決。程式碼使用了 DFS (更具體地說是 Flood Fill 演算法) 來遍歷相鄰的水域單元格，並計算水域的面積。
- 輸入處理: 讀取網格的尺寸和每個單元格的類型（'L' 或 'W'）。
- DFS 遍歷: 對於每個水域單元格，啟動 DFS 遍歷。在 DFS 過程中，將訪問過的單元格標記為已訪問（將其值設為 0），並遞迴地訪問其相鄰的水域單元格。
- 面積計算: 在 DFS 遍歷過程中，統計訪問的水域單元格的數量，這就是該水域的面積。
- 查詢處理: 對於每個查詢座標，直接返回對應單元格中儲存的水域面積。如果該單元格是陸地，則面積為 0。
複雜度分析
- 時間複雜度: O(N*M + Q)，其中 N 是網格的行數，M 是網格的列數，Q 是查詢的數量。遍歷整個網格需要 O(N*M) 的時間，處理每個查詢需要 O(1) 的時間。
- 空間複雜度: O(N*M)，主要用於儲存網格和遞迴調用的堆疊空間。在最壞的情況下，整個網格都是水域，DFS 遞迴的深度可能達到 N*M。
程式碼
#include <iostream>
using namespace std;
int mp[105][105],re[105][105],t,v,n,m,s;
string input;
void dfs(int x,int y){
if(x<0||x>=n||y<0||y>=m||mp[x][y]==0)
return;
re[x][y]=-1;
++v;
mp[x][y]=0;
for(int i=-1;i<=1;++i)
for(int j=-1;j<=1;++j)
dfs(x+i,y+j);
}
void upd(){
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(re[i][j]==-1)
re[i][j]=v;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t >> ws;
while(t--){
if(s==1)cout << "\n";
s=1;m=0;
for(int i=0;i<105;++i)
for(int j=0;j<105;++j)
mp[i][j]=re[i][j]=0;
while(isalpha(cin.peek())){
getline(cin,input);
n=input.length();
for(int i=0;i<n;++i)
(input[i]=='L')?mp[i][m]=0:mp[i][m]=-1;
++m;
}
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(mp[i][j]==-1){
v=0;
dfs(i,j);
upd();
}
while(isdigit(cin.peek())){
int x,y;
cin >> x >> y >> ws;
cout << re[y-1][x-1] << "\n";
}
}
}