Depth-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 DFS can also be used to solve this problem: once we find an element of 1, we can expand the searching in four directions. To avoid redundant scans, we need to label the positions visited. Once the search is done, the count of island is updated by adding one.

Similar to the BFS, a trick is used in the for loop for the four direction expansion, 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++;
                    dfs(grid, vis, i, j);
                }
            }
        }
        return res;
    }
private:
    void dfs(vector<vector<char>>& g, vector<vector<int>>& v, int a, int b){
        // end conditions
        if(a<0 || a>=g.size() || b<0 || b>=g.front().size() || v[a][b] || g[a][b] == '0') return;
        v[a][b] = 1;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        for(int i=0; i+1<dirs.size(); ++i) {
            int x = dirs[i] + a, y = dirs[i+1] + b;
            dfs(g, v, x, y);
        }
    }
};

Upper Layer