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';
}