Breadth-first Search - Example

Breadth-first Search - Example

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.

Constraints:

m == grid.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] is '0' or '1'.

Analysis:

The BFS method is straightforward: once we find a position with value of '1', then we can start the layer-by-layer expansion. To avoid redundant scan, we need to label the positions visited. Once the search is done, the count of island is updated by adding one.

For the four direction expansion, a trick is used in the for loop, to short the code.

See the code below:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(!grid.size() || !grid.front().size()) return 0;
        int res=0, m=grid.size(), n=grid.front().size();
        vector<vector<int>> vis(m, vector<int>(n, 0));
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j] == '1' && !vis[i][j]){
                    res++;
                    bfs(grid, vis, i, j);
                }
            }
        }
        return res;
    }
private:
    void bfs(vector<vector<char>>& g, vector<vector<int>>& v, int a, int b){
        vector<int> dirs = {-1, 0, 1, 0, -1};
        queue<pair<int, int>> q;
        q.push({a, b});
        v[a][b] = 1;
        while(q.size()) {
            auto t = q.front();
            q.pop();
            for(int i=0; i+1<dirs.size(); ++i) {
                int x = dirs[i] + t.first, y = dirs[i+1] + t.second;
                if(x<0 || x>=g.size() || y<0 || y>=g.front().size() || g[x][y] == '0' || v[x][y]) continue;
                q.push({x, y});
                v[x][y] = 1;
            }
        }
    }
};

Upper Layer