clean C++ DFS solution.


  • 2
    S
    class Solution {
    private:
        vector<vector<bool>> visited;
        int no_of_rows;
        int no_of_cols;
    public:
        int numIslands(vector<vector<char>>& grid) {
            int no_of_islands = 0;
            no_of_rows = grid.size();
            if (no_of_rows < 1) return 0;
            no_of_cols = grid[0].size();
            if (no_of_cols < 1) return 0;
            
            visited.resize(no_of_rows, std::vector<bool>(no_of_cols, false));
            for (int i = 0; i < no_of_rows; ++i){
                for (int j = 0; j < no_of_cols; ++j){
                    if (!visited[i][j] && grid[i][j] == '1'){
                        ++no_of_islands;
                        numIslands(i, j, grid);
                    }
                }
            }
            
            return no_of_islands;
        }
        void numIslands(int row, int col, vector<vector<char>>& grid) {
            if ((row < 0 || row > no_of_rows -1) || (col < 0 || col > no_of_cols - 1)) return;
            if (grid[row][col] != '1') return;
            if (visited[row][col]) return;
            
            visited[row][col] = true;
            
            numIslands(row - 1, col, grid);
            numIslands(row + 1, col, grid);
            numIslands(row, col - 1, grid);
            numIslands(row, col + 1, grid);
        }
    
    };
    

Log in to reply
 

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