LeetCode-Problems/200-Number-of-Islands.cpp at main · zeyadwaleed003/LeetCode-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool vis[305][305];
    vector<int>dx = {1, -1, 0, 0};
    vector<int>dy = {0, 0, 1, -1};
    int n, m;
    bool valid( int x, int y ){ return x >= 0 && x < n && y >= 0 && y < m; }
    void dfs( int x, int y, vector<vector<char>>& grid )
    {
        vis[x][y] = 1;
        for( int i = 0; i < 4; i++ )
        {
            int nx = x + dx[i], ny = y + dy[i];
            if( valid( nx, ny ) && grid[nx][ny] == '1' && !vis[nx][ny] )
                dfs( nx, ny, grid );
        }
    }

    int numIslands(vector<vector<char>>& grid)
    {
        n = grid.size(), m = grid[0].size();

        int cnt = 0;
        for( int i = 0; i < n; i++ )
        {
            for( int j = 0; j < m; j++ )
            {
                if( grid[i][j] == '1' && !vis[i][j] )
                {
                    dfs(i, j, grid);
                    cnt++;
                }
            }
        }

        return cnt;
    }
};