C++ BFS flood 55ms 97%


  • 0
    B
    class Solution {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            vector<pair<int, int>> ans;
            if(matrix.empty() || matrix[0].empty()) return ans;
            int r = matrix.size(), c = matrix[0].size();
            vector<vector<int>>pac(r, vector<int>(c,0));
            auto atl = pac;
            deque<pair<int,int>>aq,pq;
            
            for(int i = 0; i < r; i++)
            {
                atl[i][c-1] = pac[i][0] = 1;
                aq.push_back(make_pair(i,c-1));
                pq.push_back(make_pair(i,0));
            }
            
            for(int i = 0; i < c; i++) 
            {
                atl[r-1][i] = pac[0][i] = 1;
                aq.push_back(make_pair(r-1,i));
                pq.push_back(make_pair(0,i));
            }
            
            while(!aq.empty())
            {
                int m = aq.front().first;
                int n = aq.front().second;
                aq.pop_front();
                if(m>0 && atl[m-1][n] == 0 && matrix[m-1][n]>=matrix[m][n])
                {
                    atl[m-1][n] = 1;
                    aq.push_back(make_pair(m-1,n));
                }
                
                if(n>0 && atl[m][n-1] == 0 && matrix[m][n-1]>=matrix[m][n])
                {
                    atl[m][n-1] = 1;
                    aq.push_back(make_pair(m,n-1));
                }
                
                if(m+1 < r && atl[m+1][n] == 0 && matrix[m+1][n]>=matrix[m][n])
                {
                    atl[m+1][n] = 1;
                    aq.push_back(make_pair(m+1,n));
                }
                
                if(n+1 < c && atl[m][n+1] == 0 && matrix[m][n+1]>=matrix[m][n])
                {
                    atl[m][n+1] = 1;
                    aq.push_back(make_pair(m,n+1));
                }
            }
            
            while(!pq.empty())
            {
                int m = pq.front().first;
                int n = pq.front().second;
                pq.pop_front();
                if(m>0 && pac[m-1][n] == 0 && matrix[m-1][n]>=matrix[m][n])
                {
                    pac[m-1][n] = 1;
                    pq.push_back(make_pair(m-1,n));
                }
                
                if(n>0 && pac[m][n-1] == 0 && matrix[m][n-1]>=matrix[m][n])
                {
                    pac[m][n-1] = 1;
                    pq.push_back(make_pair(m,n-1));
                }
                
                if(m+1 < r && pac[m+1][n] == 0 && matrix[m+1][n]>=matrix[m][n])
                {
                    pac[m+1][n] = 1;
                    pq.push_back(make_pair(m+1,n));
                }
                
                if(n+1 < c && pac[m][n+1] == 0 && matrix[m][n+1]>=matrix[m][n])
                {
                    pac[m][n+1] = 1;
                    pq.push_back(make_pair(m,n+1));
                }
            }
            
            for(int i = 0; i < r; i++)
                for(int j = 0; j < c; j++)
                    if(atl[i][j] && pac[i][j]) ans.push_back(make_pair(i,j));
                    
            return ans;
        }
    };

Log in to reply
 

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