C++ _ 13ms


  • 0

    //DFS method
    Thanks : https://discuss.leetcode.com/topic/16859/12-ms-easy-c-solution-with-detailed-explanations/2

    I think the most important thoughts is:
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure

    class Solution {
    public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> check(m,vector<bool>(n,false));
        int island = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!check[i][j] && grid[i][j] == '1')
               {
                    island++;
                    check[i][j] = true;
                    find(grid, check, i, j, m, n);
                }
            }
        }
        return island;
    }
    
    void find(vector<vector<char>>& grid, vector<vector<bool>>& check, int i, int j, int m, int n){
        if(i - 1 >= 0 && !check[i-1][j] && grid[i-1][j] == '1'){
            check[i-1][j] = true;
            find(grid, check, i-1, j, m, n);
        }
        if(j - 1 >= 0 && !check[i][j-1] && grid[i][j-1] == '1'){
            check[i][j-1] = true;
            find(grid, check, i, j-1, m, n);
        }
        if(i + 1 < m && !check[i+1][j] && grid[i+1][j] == '1'){
            check[i+1][j] = true;
            find(grid, check, i+1, j, m, n);
        }
        if(j + 1 < n && !check[i][j+1] && grid[i][j+1] == '1'){
            check[i][j+1] = true;
            find(grid, check, i, j+1, m, n);
        }
        return;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.