Leetcode Study Day 42

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.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
 

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Solution

I saw a wonderful solution using DFS to solve this question in python. I convert it into C++ version.

In this code, we frist iterate the grid from the top left corner to the bottom right corner. If we find a ‘1’, we use dfs to find all the adjacent ‘1’ and change them into ‘#’. Then we increase the count by 1. Finally, we return the count.

class Solution {
public:
    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-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty())
            return 0;
        int count = 0;
        for (int i = 0;i < grid.size(); i ++){
            for (int j = 0; j < grid[0].size(); j++){
                if (grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count ++;
                }
            }
        }
        return count;
    }
};