Jerry's Notes

LeetCode 200. Number of Islands

DFS BFS
Word count: 427Reading time: 2 min
2022/01/24

LeetCode 200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Method 1 BFS

Code

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
39
class Solution {
public:
    
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if (!row) return 0;
        int col = grid[0].size();
        
        vector<vector<int> > dirs = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; // 4 directions of a position
        int res = 0;
        queue<pair<int, int>> que; 
        //queue<int> q;   x = curr / m; y = curr % m;
        
        // Traverse all points in the array
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    grid[i][j] = '0';
                    // BFS
                    que.push({i, j});
                    while (!que.empty()) {
                        int m = que.front().first, n = que.front().second; // m - x coordinates, n - y coordinates
                        que.pop();
                        for (auto dir : dirs) {
                            int x = m + dir[0];
                            int y = n + dir[1];
                            if (x < 0 || y < 0 || x > row - 1 || y > col - 1 || grid[x][y] != '1') // x < 0 || y < 0 || x > row - 1 || y > col - 1 -- out of bounds, grid[x][y] != '1' -- not island
                                continue;
                            grid[x][y] = '0';
                            que.push({x, y});
                        }
                    }
                }
            }
        }
        return res;
    }
};

Methos 2 DFS

Code

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
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return res;
    }
    
    void dfs(vector<vector<char>>& grid, int i , int j){
        if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != '1')
            return;
        
        grid[i][j] = '#';
        
        dfs(grid, i-1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
        dfs(grid, i+1, j);
        
    }
};
Total : 15
2022
Sliding Window BST Dynamic Programming Research Project DFS Permutations Binary Tree Sort BFS love-letter
LeetCode Algorithms for Sensor-Based Robotics Rambling Digression