C++ BFS 53ms


  • 0
    R
    class Solution {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            if (matrix.empty() || matrix[0].empty()) return {};
            int m = (int) matrix.size(), n = (int) matrix[0].size();
            int pm[m][n];
            fill_n(&pm[0][0], m * n, false);
            int am[m][n];
            fill_n(&am[0][0], m * n, false);
            queue<pair<int, int>> pq; // next point for pacific bfs;
            queue<pair<int, int>> aq; // next point for atlantic bfs;
            vector<pair<int, int>> res;
            for (int i = 0; i < m; i++) {
                int j = m - i - 1;
                pm[i][0] = 1;
                pq.push({i, 0});
                am[j][n-1] = 1;
                aq.push({j, n-1});
            }
            for (int i = 1; i < n; i++) {
                int j = n - i - 1;
                pm[0][i] = 1;
                pq.push({0, i});
                am[m-1][j] = 1;
                aq.push({m-1, j});
            }
            while (!pq.empty()) {
                pair<int, int> point = pq.front();
                int x = point.first, y = point.second;
                pq.pop();
                if (x-1 >= 0 && !pm[x-1][y] && matrix[x-1][y] >= matrix[x][y]) {
                    pq.push({x-1, y});
                    pm[x-1][y] = 1;
                }
                if (x+1 < m && !pm[x+1][y] && matrix[x+1][y] >= matrix[x][y]) {
                    pq.push({x+1, y});
                    pm[x+1][y] = 1;
                }
                if (y-1 >= 0 && !pm[x][y-1] && matrix[x][y-1] >= matrix[x][y]) {
                    pq.push({x, y-1});
                    pm[x][y-1] = 1;
                }
                if (y+1 < n && !pm[x][y+1] && matrix[x][y+1] >= matrix[x][y]) {
                    pq.push({x, y+1});
                    pm[x][y+1] = 1;
                }
            }
            while (!aq.empty()) {
                pair<int, int> point = aq.front();
                int x = point.first, y = point.second;
                if (am[x][y] && pm[x][y]) res.push_back({x,y});
                aq.pop();
                if (x-1 >= 0 && !am[x-1][y] && matrix[x-1][y] >= matrix[x][y]) {
                    aq.push({x-1, y});
                    am[x-1][y] = 1;
                }
                if (x+1 < m && !am[x+1][y] && matrix[x+1][y] >= matrix[x][y]) {
                    aq.push({x+1, y});
                    am[x+1][y] = 1;
                }
                if (y-1 >= 0 && !am[x][y-1] && matrix[x][y-1] >= matrix[x][y]) {
                    aq.push({x, y-1});
                    am[x][y-1] = 1;
                }
                if (y+1 < n && !am[x][y+1] && matrix[x][y+1] >= matrix[x][y]) {
                    aq.push({x, y+1});
                    am[x][y+1] = 1;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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