e550 - 00722 - Lakes
題目描述
題目要求計算一個二維網格中，以指定座標為起點的連通水域（'0'）的面積。水域必須被陸地（'1'）完全包圍。
解題思路
使用深度優先搜尋 (DFS) 演算法來遍歷連通的水域。從給定的起點座標開始，將相鄰的 '0' 標記為 '1'（已訪問），並遞迴地對其相鄰的 '0' 進行相同的操作。在遍歷過程中，統計訪問的 '0' 的數量，即為水域的面積。
複雜度分析
- 時間複雜度: O(N*M)，其中 N 是網格的行數，M 是網格的列數。在最壞的情況下，DFS 可能需要遍歷整個網格。
- 空間複雜度: O(NM)，在最壞的情況下，遞迴調用堆疊的深度可能達到 NM。
程式碼
#include <iostream>
using namespace std;
int xg,yg,t,n,m,ans;
string input;
char a[101][101];
void dfs(int x,int y){
if(x>=n||y>=m||x<0||y<0||a[x][y]=='1'){
return;
}
++ans;
a[x][y]='1';
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 >> t;
int s=0;
while(t--){
if(s)
cout << "\n";
s=1;
for(int i=0;i<101;++i)
for(int j=0;j<101;++j)
a[i][j]='1';
cin >> xg >> yg;
getline(cin,input);
n=m=ans=0;
while(getline(cin,input)&&input.size()){
m=input.length();
for(int i=0;i<m;++i)
a[n][i]=input[i];
++n;
}
if(xg-1>=n||yg-1>=m)
cout << "0\n";
else{
dfs(xg-1,yg-1);
cout << ans << "\n";
}
}
}