Skip to main content

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



Comments

Popular posts from this blog

Trie

Trie is a data structure belonging to n-ary trees, which is designed for some specific questions, such as, prefix of strings. (If you have never known what binary tree is, maybe you can check binary tree first before read more about Trie). The fact that there are only 26 different letters greatly reduce the possible choices for each position. Or to make it clear, for each position, there are 26 different choices. In mathematics, it seems to be very large (height^26 for the full tree), but in reality, it is rare to be a full tree for the set of meaningful strings (needs at least height^26 strings to be a full tree!), since the height or length of English words are less than 10 in most cases. Therefore, it is popular in string matching or related operations. Please be noted that the trie structure is not only limited to strings, the same idea can be extended to other data types, such as integer (then it becomes a binary tree, since for bit, there are only two possible values). In the cod...

Dynamic Programming - Hard Level - Question 1

Dynamic Programming - Hard Level - Question 1  Leetcode 1937  Maximum Number of Points with Cost You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score. Return the maximum number of points you can achieve. abs(x) is defined as: x for x >= 0. -x for x < 0. Constraints: m == points.length n == points[r].length 1 <= m, n <= 10^5 1 <= m * n <= 10^5 0 <= points[r][c] <= 10^5 Analysis: Based on the description, we can define dp[i][j] as the maximum number of points wit...