Got TLE by bfs with queue C++


  • 0
    X

    My recursive implementation of bfs is accepted but this version with queue causes TLE.
    last input: ["11111011111111101011","01111111111110111110","10111001101111111111","11110111111111111111","10011111111111111111","10111111011101110111","01111111111101101111","11111111111101111011","11111111110111111111","11111111111111111111","01111111011111111111","11111111111111111111","11111111111111111111","11111011111110111111","10111110111011110111","11111111111101111110","11111111111110111100","11111111111111111111","11111111111111111111","11111111111111111111"]
    My code
    class Solution {
    public:
    void dilute(vector<vector<char> > &grid, int i, int j){
    if(i>0&&grid[i-1][j]=='1'){
    grid[i-1][j]='0';
    dilute(grid, i-1, j);
    }
    if(j>0&&grid[i][j-1]=='1'){
    grid[i][j-1]='0';
    dilute(grid, i, j-1);
    }
    if(i<grid.size()-1&&grid[i+1][j]=='1'){
    grid[i+1][j]='0';
    dilute(grid, i+1, j);
    }
    if(j<grid[0].size()-1&&grid[i][j+1]=='1'){
    grid[i][j+1]='0';
    dilute(grid, i, j+1);
    }
    }

    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()<=0)
            return 0;
        vector<vector<int>> sign(grid.size(),vector<int> (grid[0].size()));
        int i,count=0,j;
        queue<vector<int>> q;
        for(i=0;i<grid.size();i++)
        {
            for(j=0;j<grid[0].size();j++)
            {
                if(grid[i][j] == '1')
                {
                    count++;
                   // dilute(grid,i,j);
                    
                    q.push({i,j});
                    for(;q.size()>0;)
                    {
                        vector<int> cor = q.front();
                        q.pop();
                        grid[cor[0]][cor[1]]='0';
                    
                        if(cor[0]>0 && grid[cor[0]-1][cor[1]]=='1')
                            q.push({cor[0]-1,cor[1]});
                        if(cor[1]>0 && grid[cor[0]][cor[1]-1]=='1')
                            q.push({cor[0],cor[1]-1});
                        if(cor[0]<grid.size()-1 && grid[cor[0]+1][cor[1]]=='1')
                            q.push({cor[0]+1,cor[1]});
                        if(cor[1]<grid[0].size()-1 && grid[cor[0]][cor[1]+1]=='1')
                            q.push({cor[0],cor[1]+1});
                        
                        
                    }
                
                }
            }
        }
        return count;
        
    }
    

    };


Log in to reply
 

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