My C++ DFS solution, 9ms


  • 2
    E
    int numIslands(vector<vector<char>> &grid) 
    {
        int m = grid.size();
        if(m <= 0)
            return 0;
        int n = grid[0].size();
        int ret = 0;
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(grid[i][j] == '1')
                {
                    ++ret;
                    DFS(grid, i, j);
                }
            }
        }
        return ret;
    }
    
    void DFS(vector<vector<char>> &grid, int i, int j)
    {
        grid[i][j] = '0';
        if(i > 0 && grid[i-1][j] == '1')
            DFS(grid, i-1, j);
        if(i < grid.size()-1 && grid[i+1][j] == '1')
            DFS(grid, i+1, j);
        if(j > 0 && grid[i][j-1] == '1')
            DFS(grid, i, j-1);
        if(j < grid[0].size()-1 && grid[i][j+1] == '1')
            DFS(grid, i, j+1);
    }

  • 0
    R

    Great solution. It's just is it proper to edit the input 'grid' in order to get the answer? I think the 'grid' might be read-only as an input to this API.


  • 0
    P

    I think it's Ok, if the 'grid' is restricted to be read-only, then the parameter should be 'const vector<vector<char>> &grid'


Log in to reply
 

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