417.太平洋大西洋水流问题

链接：417.太平洋大西洋水流问题
难度：Medium
标签：深度优先搜索、广度优先搜索、数组、矩阵
简介：返回 网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。

题解 1 - cpp

• 编辑时间：2022-04-27
• 执行用时：28ms
• 内存消耗：18MB
• 编程语言：cpp
• 解法介绍：dfs，上山。

int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
class Solution {
   public:
    int n, m;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        n = heights.size(), m = heights[0].size();
        vector<vector<int>> arr(n, vector(m, 0));
        for (int row = 0; row < n; row++) {
            arr[row][0] |= 0b01;
            arr[row][m - 1] |= 0b10;
            dfs(row, 0, arr, heights);
            dfs(row, m - 1, arr, heights);
        }
        for (int col = 0; col < m; col++) {
            arr[0][col] |= 0b01;
            arr[n - 1][col] |= 0b10;
            dfs(0, col, arr, heights);
            dfs(n - 1, col, arr, heights);
        }
        vector<vector<int>> ans;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                if (arr[row][col] != 0b11) continue;
                vector<int> item(2);
                item[0] = row;
                item[1] = col;
                ans.push_back(item);
            }
        }
        return ans;
    }
    void dfs(int row, int col, vector<vector<int>>& arr,
             vector<vector<int>>& heights) {
        for (int i = 0; i < 4; i++) {
            int nrow = row + dirs[i][0], ncol = col + dirs[i][1];
            if (nrow < 0 || ncol < 0 || nrow == n || ncol == m) continue;
            if (heights[nrow][ncol] < heights[row][col]) continue;
            if (arr[row][col] == arr[nrow][ncol]) continue;
            arr[nrow][ncol] |= arr[row][col];
            dfs(nrow, ncol, arr, heights);
        }
    }
};