417. Pacific Atlantic Water Flow

bfs O(mn) time O(mn) space
这道题不能用堆+爬坡的方法，因为不是有序的，也不能用堆+灌水的方法，因为左上和右下两边是无关的，灌水法要求从外往里，每一层必须是一致的
解法：把沿海的边分别入队列，bfs爬坡标记两个海分别可以到哪些点，最后两个海都能到的点即为所求

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> v1(m, vector<bool>(n)), v2 = v1;
        int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
        bfs(matrix, 0, 0, m, n, v1, dx, dy); // 对每个沿海可达的地方标记
        bfs(matrix, m - 1, n - 1, m, n, v2, dx, dy);
        vector<vector<int>> res;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (v1[i][j] && v2[i][j]) { // 如果被标记过两次，说明这个地方两个海都可达
                    res.push_back({i, j});
                }
            }
        }
        return res;
    }

    void bfs(vector<vector<int>> &matrix, int r, int c, int m, int n, vector<vector<bool>> &v, int dx[], int dy[]) {
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) { // 把沿海的两条边入队列
            q.emplace(i, c);
            v[i][c] = true;
        }
        for (int j = 0; j < n; ++j) {
            q.emplace(r, j);
            v[r][j] = true;
        }
        while (!q.empty()) {
            int y = q.front().first, x = q.front().second; q.pop();
            for (int i = 0; i < 4; ++i) {
                int yy = y + dy[i], xx = x + dx[i];
                if (0 <= yy && yy < m && 0 <= xx && xx < n && !v[yy][xx] && matrix[yy][xx] >= matrix[y][x]) { // 爬坡
                    q.emplace(yy, xx);
                    v[yy][xx] = true;
                }
            }
        }
    }
};