C++ Backward Search using BFS


  • 2
    K

    I use two bool matrixs separately to record whether the coordinates can flow to the Pacific and Atlantic ocean or not. Each time, I push the coordinates of edges touched by one ocean into the queue, then call bfs function to update the corresponding bool matrix. Finally, the coordinates which are true both in the two bool matrixs are the answer.

    Forgive my poor English.

    struct Node
    {
        int x, y;
        Node(){}
        Node(int xx, int yy): x(xx), y(yy){}
    };
    vector<int> dx = {-1, 0, 1, 0};
    vector<int> dy = {0, 1, 0, -1};
    
    class Solution {
    public:
        int n, m;
        bool bound(int x, int y)
        {
            return x >= 0 && x < n && y >= 0 && y < m;
        }
        void bfs(vector<vector<int>>& matrix, vector<vector<bool>> &vis, queue<Node> &q)
        {
            while(!q.empty())
            {
                Node now = q.front();
                q.pop();
                for(int k = 0; k < 4; k++)
                {
                    int nx = now.x + dx[k], ny = now.y + dy[k];
                    if(bound(nx, ny) && !vis[nx][ny])
                    {
                        if(matrix[nx][ny] >= matrix[now.x][now.y])
                        {
                            vis[nx][ny] = true;
                            q.push(Node(nx, ny));
                        }
                    }
                }
            }
        }
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            vector<pair<int, int>> ans;
            n = matrix.size();
            if(n == 0) return ans;
            m = matrix[0].size();
            
            queue<Node> q;
            
            vector<vector<bool>> p(n, vector<bool>(m, 0));
            for(int i = 0; i < n; i++) 
            {
                q.push(Node(i, 0));
                p[i][0] = true;
            }
            for(int j = 0; j < m; j++) 
            {
                q.push(Node(0, j));
                p[0][j] = true;
            }
            bfs(matrix, p, q);
            
            while(!q.empty()) q.pop();
            
            vector<vector<bool>> a(n, vector<bool>(m, 0));
            for(int i = 0; i < n; i++) 
            {
                q.push(Node(i, m-1));
                a[i][m-1] = true;
            }
            for(int j = 0; j < m; j++) 
            {
                q.push(Node(n-1, j));
                a[n-1][j] = true;
            }
            bfs(matrix, a, q);
            
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    if(p[i][j] && a[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.