C++ || BFS || TLE when used queue ||Why??
Ashay Jain
46

Thanks in advance !
THIS GAVE TLE

 int numIslands(vector<vector<char>>& grid) {
        int ans=0,n=grid.size(),m=grid[0].size();
        vector<vector<bool>> vis(n,vector<bool>(m,true) );
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]=='1' && vis[i][j])
                {
                    queue<pair<int,int>> q;
                    q.push({i,j});
                    
                    pair<int,int> t;
                    while(!q.empty())
                    {
                        t=q.front();
                        q.pop();
                        int r=t.first,c=t.second;
                        vis[r][c]=false;
                        if(r>0 && grid[r-1][c]=='1' && vis[r-1][c]) q.push({r-1,c});
                        if(c>0 && grid[r][c-1]=='1' && vis[r][c-1]) q.push({r,c-1});
                        if(r<n-1 && grid[r+1][c]=='1' && vis[r+1][c]) q.push({r+1,c});
                        if(c<m-1 && grid[r][c+1]=='1' && vis[r][c+1]) q.push({r,c+1});
                        
                    }
                    ans++;
                }
            }
        }
        return ans;
    }

But This worked fine

 int numIslands(vector<vector<char>>& grid) {
        int ans=0,n=grid.size(),m=grid[0].size();
        vector<vector<bool>> vis(n,vector<bool>(m,true) );
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]=='1' && vis[i][j])
                {
                    stack<pair<int,int>> q;
                    q.push({i,j});
                    
                    pair<int,int> t;
                    while(!q.empty())
                    {
                        t=q.top();
                        q.pop();
                        int r=t.first,c=t.second;
                        vis[r][c]=false;
                        if(r>0 && grid[r-1][c]=='1' && vis[r-1][c]) q.push({r-1,c});
                        if(c>0 && grid[r][c-1]=='1' && vis[r][c-1]) q.push({r,c-1});
                        if(r<n-1 && grid[r+1][c]=='1' && vis[r+1][c]) q.push({r+1,c});
                        if(c<m-1 && grid[r][c+1]=='1' && vis[r][c+1]) q.push({r,c+1});
                        
                    }
                    ans++;
                }
            }
        }
        return ans;
    }
Comments (1)