DFS 島嶼數

題目

給定 n×m 矩陣,由 0 和 1 組成。1 代表是島嶼,0 代表是水,請算出總共有幾個島嶼。(連在一起的 1 是一個島嶼)

輸入:
5 4
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

輸出:3

想法

從左上角[0][0]開始,如果遇到1,而且這個位置沒有走訪過,就把這個位置丟進dfs()裡,等dfs()跑完之後,答案(島嶼數)+1。

dfs(int i, int j): 把傳進來的這個i,j位置,標示為已經走過,然後看這個位置的上下左右是否也是1,如果那個位置是1且沒有超出邊界的話,就把那個位置也丟進dfs()裡。

Code

#include <iostream>
using namespace std;
int n, m;
const int MAX = 300;
int grid[MAX][MAX];
int visited[MAX][MAX];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int i, int j){
    visited[i][j] = true;
    for(int d=0; d<4; d++){
        int nx = i+dx[d];
        int ny = j+dy[d];
        if(grid[nx][ny]==1 && !visited[nx][ny] && nx>=0 && nx<n && ny>=0 && ny<m){
            dfs(nx, ny);
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> grid[i][j];
        }
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(grid[i][j]==1 && !visited[i][j]){
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << '\n';
}
發佈留言

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