【題目連結】https://zerojudge.tw/ShowProblem?problemid=e584 (請先看完題目)
【題目大意】有一個 m×n 地圖(大陸和水),且地圖左右相連,大帝在 (x, y) 的大陸上,請找出除了大帝目前所在的大陸外,最大的大陸面積。
【解法】DFS
#include <iostream>
using namespace std;
int m, n, x, y;
char grid[20][20];
char land;
bool visited[20][20];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int land_size;
void dfs(int x, int y){
visited[x][y] = true;
land_size++;
for(int d=0; d<4; d++){
int nx = x+dx[d];
int ny = y+dy[d];
if(ny >= n) ny=0;
if(ny < 0) ny=n-1;
if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny]==land && !visited[nx][ny]){
dfs(nx, ny);
}
}
}
int main(){
while(cin >> m >> n){
string s;
for(int i=0; i<m; i++){
cin >> s;
for(int j=0; j<n; j++){
visited[i][j] = false;
grid[i][j] = s[j];
}
}
cin >> x >> y;
land = grid[x][y];
dfs(x, y);
int max_ans = 0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]==land && !visited[i][j]){
land_size = 0;
dfs(i, j);
max_ans = max(land_size, max_ans);
}
}
}
cout << max_ans << '\n';
}
}