6ms c++ stack Solution, straightforward solution


  • 1
    Z

    Hi all, here I share my cpp solution using a basic data structure stack. The idea is: every time we meet a '1', we push it into stack, then we push the nearby '1' to stack and we recursively pop the stack and change '1' to '0'. The good thing about stack is that 1. easy to implement 2. safe to use(wont miss any coordinate). Stack is powerful to certain 2D grid problems like maze etc.

    bool inGrid (pair<int,int> a, const vector<vector<char>>& grid)
    {
        if(a.first>=0&&a.first<grid.size()&&a.second>=0&&a.second<grid[0].size())
            return true;
        
        return false;
    }
    
    
    void change(vector<vector<char>>& grid,stack<pair<int,int>>& coordinates)
    {
        if(coordinates.empty())
            return;
        
        pair<int,int> temp = coordinates.top();
        coordinates.pop();
        
        grid[temp.first][temp.second]='0';
    
        pair<int,int> up = {temp.first+1,temp.second};
        pair<int,int> down = {temp.first-1,temp.second};
        pair<int,int> left = {temp.first,temp.second-1};
        pair<int,int> right = {temp.first,temp.second+1};
        if(inGrid(up,grid)&&grid[up.first][up.second]=='1')
            coordinates.push(up);
        if(inGrid(down,grid)&&grid[down.first][down.second]=='1')
            coordinates.push(down);
        if(inGrid(left,grid)&&grid[left.first][left.second]=='1')
            coordinates.push(left);
        if(inGrid(right,grid)&&grid[right.first][right.second]=='1')
            coordinates.push(right);
        
        return change(grid,coordinates);
    }
    
    int numIslands(vector<vector<char>>& grid)
    {
        int count = 0;
        stack<pair<int,int>> coordinates;
        for(int row = 0;row<grid.size();row++)
            for(int col = 0; col<grid[0].size();col++)
            {
                if(grid[row][col]=='1')
                {
                    pair<int,int> current = {row,col};
                    coordinates.push(current);
                    change(grid,coordinates);
                    count++;
                }
            }
        return count;
    }

  • 0
    Z

    @zhutianqi great solution! plz reply!


Log in to reply
 

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