leetcode第417题：太平洋大西洋水流问题 [中等]

题目描述

考点

• 深度优先搜索
• 广度优先搜索

解题思路 - 深度优先搜索

1. 对矩阵的四条边，进行搜索；判断太平洋、大西洋的水可以逆向到达的区域；分别记录在矩阵：can_reach_p, can_reach_a中；
2. 综合 can_reach_p, can_reach_a 的结果，判断哪些区域的水可以下流到太平洋、大西洋；

代码实现

class Solution {
private:
    // 代表4个方向
    vector<vector<int>> directions = {{-1,0}, {0,1}, {1,0}, {0,-1}};

    // 深度优先搜索（辅函数）
    void dfs(const vector<vector<int>>& matrix, vector<vector<bool>>& can_reach, int x, int y){
        if(can_reach[x][y])
            return;
        
        can_reach[x][y] = true;
        int new_x, new_y;
        for(int i = 0; i < 4; ++i){
            new_x = x + directions[i][0];
            new_y = y + directions[i][1];

            if(new_x >= 0 && new_x < matrix.size() && new_y >= 0 && new_y < matrix[0].size() 
                && matrix[x][y] <= matrix[new_x][new_y]){
                dfs(matrix, can_reach, new_x, new_y);
            }
        }
    }
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> ans;
        // 判断是否为空
        if(matrix.empty() || matrix[0].empty())
            return ans;
        
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> can_reach_p(m, vector<bool>(n, false));
        vector<vector<bool>> can_reach_a(m, vector<bool>(n, false));

        // 搜索矩阵的4条边；判断水流可以逆向到达的区域；
        for(int i = 0; i < m; ++i){
            dfs(matrix, can_reach_p, i, 0);
            dfs(matrix, can_reach_a, i, n-1);
        }
        for(int i = 0; i < n; ++i){
            dfs(matrix, can_reach_p, 0, i);
            dfs(matrix, can_reach_a, m-1, i);
        }

        // 综合判断：can_reach_p 记录可以到达太平洋的区域，can_reach_a 记录可以到达大西洋的区域；
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(can_reach_p[i][j] && can_reach_a[i][j]){
                    ans.push_back(vector<int>{i, j});
                }
            }
        }
        return ans;
    }
};