【題解】ZeroJudge e584: 11094 – Continents

【題目連結】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';
    }
}
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *