C++ BFS


  • 1
    class Solution {
    public:
        void flow(int i, int j, vector<vector<int>>& map, vector<vector<int>>& visit) {
            if(visit[i][j]==1) return;
            queue<pair<int,int>> q;
            q.push({i,j});
            int m = map.size();
            int n = map[0].size();
            while(!q.empty()) {
                auto p = q.front();
                q.pop();
                int x = p.first;
                int y = p.second;
                if(visit[x][y] == 1) continue;
                visit[x][y] = 1;
                if(x>0 && map[x-1][y]>=map[x][y]) q.push({x-1,y});
                if(y>0 && map[x][y-1]>=map[x][y]) q.push({x,y-1});
                if(x<m-1 && map[x+1][y]>=map[x][y]) q.push({x+1,y});
                if(y<n-1 && map[x][y+1]>=map[x][y]) q.push({x,y+1});
            }
        }
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            int m = matrix.size();
            if(m==0) return {};
            int n = matrix[0].size();
            if(n==0) return {};
            vector<vector<int>> pac(m,vector<int>(n,0));
            vector<vector<int>> atl(m,vector<int>(n,0));
            vector<pair<int,int>> ans;
            
            for(int i=0;i<m;i++) {
                flow(i,0,matrix,pac);
                flow(i,n-1,matrix,atl);
            }
            
            for(int i=0;i<n;i++) {
                flow(0,i,matrix,pac);
                flow(m-1,i,matrix,atl);
            }
            
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(pac[i][j]==1 && atl[i][j]==1) ans.push_back({i,j});
                }
            }
    
            return ans;
        }
    };
    

  • 0

    Good solution and very clear.
    One suggestion: you can actually use just one visited and make it "+1" as pac, "+2" as atl. Then finally check whether the cell is 3. That saves some space (but very minor though)


Log in to reply
 

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