46 ms C++ BFS Solution


  • 2
    R

    Two vectors that store expansion from each ocean.
    Return the intersections of those two vectors.

    class Solution {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            vector<pair<int,int>> res;
            int m = matrix.size();
            if (m == 0) return res;
            int n = matrix[0].size();
            
            vector<vector<int>> atop(m,vector<int>(n,0));
            vector<vector<int>> ptoa(m,vector<int>(n,0));
            
            pathAP(atop, matrix);
            pathPA(ptoa, matrix);
            
            checkpair(atop, ptoa, res);
            return res;
        }
        
        void checkpair(vector<vector<int>> &atop, vector<vector<int>> &ptoa, vector<pair<int,int>>& res) {
            for (int i = 0; i < atop.size(); ++i) {
                for (int j = 0; j < atop[0].size(); ++j) {
                    if (atop[i][j] == 1 && ptoa[i][j] == 1) {
                        res.push_back(make_pair(i,j));
                    }
                }
            }
        }
        
        void pathAP(vector<vector<int>> &atop, vector<vector<int>>& matrix) {
            vector<vector<bool>> visited(matrix.size(),vector<bool>(matrix[0].size(),false));
            for (int i = 0; i < matrix.size(); ++i) {
                bfs(atop, matrix, visited, i, 0);
            }
            for (int j = 0; j < matrix[0].size(); ++j) {
                bfs(atop, matrix, visited, 0, j);
            }
            updatePath(atop, visited);
        }
        
        void pathPA(vector<vector<int>> &ptoa, vector<vector<int>>& matrix) {
            vector<vector<bool>> visited(matrix.size(),vector<bool>(matrix[0].size(),false));
            for (int i = 0; i < matrix.size(); ++i) {
                bfs(ptoa, matrix, visited, i, matrix[0].size()-1);
            }
            
            for (int j = 0; j < matrix[0].size(); ++j) {
                bfs(ptoa, matrix, visited, matrix.size()-1, j);
            }
            
            updatePath(ptoa, visited);
            
        }
        
        void bfs(vector<vector<int>> &ptoa, vector<vector<int>>& matrix, vector<vector<bool>>& visited, int row, int col) {
            visited[row][col] = true;
            
            int curr = matrix[row][col];
            if (row > 0 && !visited[row-1][col] && matrix[row-1][col] >= curr) bfs(ptoa, matrix, visited, row-1, col);
            if (col > 0 && !visited[row][col-1]  && matrix[row][col-1] >= curr) bfs(ptoa, matrix, visited, row, col-1);
            if (row < matrix.size() -1 && !visited[row+1][col] && matrix[row+1][col] >= curr) bfs(ptoa, matrix, visited, row+1, col);
            if (col < matrix[0].size() -1 && !visited[row][col+1] && matrix[row][col+1] >= curr) bfs(ptoa, matrix, visited, row, col+1);
        }
    
        void updatePath(vector<vector<int>> &board, vector<vector<bool>>& visited) {
            for (int i = 0; i < visited.size(); ++i) {
                for (int j = 0; j < visited[0].size(); ++j) {
                    if (visited[i][j] && board[i][j] == 0) {
                        board[i][j] = 1;
                    }
                }
            }
        }
    };
    

Log in to reply
 

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