C++ dfs solution


  • 0
    N
    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            int ret = 0;
            if (grid.empty()) return ret;
            vector<vector<bool>> h(grid.size(), vector<bool>(grid[0].size(), false));
            for (int i = 0; i < grid.size(); ++ i)
                for (int j = 0; j < grid[0].size(); ++ j)
                    if (grid[i][j] == '1' && h[i][j] == false){
                        h[i][j] = true;
                        dfs(i, j, grid, h);
                        ret ++;
                    }
            return ret;
        }
    
    private:
        const int tx[4] = {0, 0, 1, -1},
                  ty[4] = {1, -1, 0, 0};
        void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<bool>>& h){
            for (int i = 0; i < 4; ++ i)
                if (x + tx[i] >= 0 && x + tx[i] < grid.size() 
                 && y + ty[i] >= 0 && y + ty[i] < grid[0].size()
                 && grid[x + tx[i]][y + ty[i]] == '1' && h[x + tx[i]][y + ty[i]] == false){
                     h[x + tx[i]][y + ty[i]] = true;
                     dfs(x + tx[i], y + ty[i], grid, h);
                 }
        }
    
    };
    

Log in to reply
 

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