e584 - 11094 - Continents
題目描述
題目要求找出地圖上除了 Mijid 大帝所在大陸之外，最大的大陸面積。地圖由陸地和水域組成，大陸定義為相連的陸地區域，邊界為水域或地圖邊緣。地圖的左右邊緣相連，形成環狀結構。
解題思路
本題可以使用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 來解決。程式碼採用 DFS 的方式。首先，讀取地圖和 Mijid 大帝所在的座標。然後，使用 DFS 找出 Mijid 大帝所在的大陸，並將該大陸上的所有陸地標記為已訪問（例如，替換為空格）。接著，遍歷整個地圖，如果遇到未訪問的陸地，則使用 DFS 計算該大陸的面積，並更新最大大陸面積。最後，輸出最大大陸面積。由於地圖的左右邊緣相連，DFS 函數需要考慮邊界情況。
複雜度分析
- 時間複雜度: O(M * N)，其中 M 和 N 是地圖的行數和列數。因為最壞情況下，需要遍歷整個地圖來尋找所有大陸。
- 空間複雜度: O(M * N)，主要來自於地圖陣列
mp和 DFS 的遞迴堆疊空間。在最壞情況下，整個地圖都是陸地，DFS 的遞迴深度可能達到 M * N。
程式碼
#include <iostream>
using namespace std;
char mp[21][21],l;
int x,y,a,b,ans;
inline void dfs(int xx,int yy){
if(xx>=x||yy>=y||xx<0||yy<0||mp[xx][yy]!=l)return;
mp[xx][yy]=' ';
++ans;
dfs(xx+1,yy);
dfs(xx-1,yy);
dfs(xx,yy+1);
dfs(xx,yy-1);
if(yy==0)
dfs(xx,y-1);
if(yy==y-1)
dfs(xx,0);
}
inline void clear(int xx,int yy){
if(xx>=x||yy>=y||xx<0||yy<0||mp[xx][yy]!=l)return;
mp[xx][yy]=' ';
dfs(xx+1,yy);
dfs(xx-1,yy);
dfs(xx,yy+1);
dfs(xx,yy-1);
if(yy==0)
dfs(xx,y-1);
if(yy==y-1)
dfs(xx,0);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> x >> y){
int maxn=0;
for(int i=0;i<x;++i)
for(int j=0;j<y;++j)
cin >> mp[i][j];
ans=0;
cin >> a >> b;
l=mp[a][b];
clear(a,b);
for(int i=0;i<x;++i)
for(int j=0;j<y;++j)
if(mp[i][j]==l){
ans=0;
dfs(i,j);
maxn=max(maxn,ans);
}
cout << maxn << "\n";
}
}