【04-27】力扣每日一题

今天的题目是深搜和广搜的类型呢

题目描述

题目分析

这道题目通俗来讲就是，现在有一个二维数组，数组里的值代表着比海平面高出多少。对于一个二维数组而言，左边和上边与太平洋相接，而右边和下边与大西洋相接。只要与海相接雨水都能够流进大海。而在这个二维数组中，如果一个格子的值大于相邻格子的值，那么雨水就能够从本格子流到相邻的格子（水往低处流）。现在需要找到这个二维数组中，哪些格子里的雨水既可以流入太平洋，有可以流入大西洋。

经过上述分析之后，那么自然而然就能够想到使用深度优先搜索了。我们的思路是，从二维数组的四个边界出发，寻找上升序列，从太平洋边界出发的，到达的地方我们用二维布尔数组记录。同样从大西洋边界出发的，到达的地方我们用另外一个布尔数组记录。最后我们只需要取这两个数组的交集即可。

而在遍历的时候就是我们通用的深度优先遍历的方法了，定义方向数组，枚举起点，然后每次dfs的时候判断下标是否有效并且是否被访问过，然后在dfs中递归调用dfs。

代码实现

c++代码如下：

class Solution {
    // 行数和列数
    int rows = 0,cols = 0;
    // 返回的结果
    vector<vector<int>> res;
    // 上右下左四个方向
    int direction[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        // 深度优先搜索
        rows = heights.size();
        cols = heights[0].size();
        vector<vector<bool>> pacific(rows,vector<bool>(cols));
        vector<vector<bool>> atlantic(rows,vector<bool>(cols));
        for(int i=0;i<rows;i++){
            pacific[i][0] = true;
            dfs(i,0,heights,pacific);
        }
        for(int i=0;i<cols;i++){
            pacific[0][i] = true;
            dfs(0,i,heights,pacific);
        }
        for(int i=0;i<cols;i++){
            atlantic[rows-1][i] = true;
            dfs(rows-1,i,heights,atlantic);
        }
        for(int i=0;i<rows;i++){
            atlantic[i][cols-1] = true;
            dfs(i,cols-1,heights,atlantic);
        }
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(pacific[i][j] && atlantic[i][j]){
                    vector<int> tmp;
                    tmp.push_back(i);
                    tmp.push_back(j);
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }

    void dfs(int x,int y,vector<vector<int>> &heights,vector<vector<bool>> &record){
        for(int i = 0;i<4;i++){
            int xx = x+direction[i][0];
            int yy = y+direction[i][1];
            if(xx>=0 && xx<rows && yy>=0 && yy<cols && !record[xx][yy] && heights[xx][yy]>=heights[x][y]){
                record[xx][yy] = true;
                dfs(xx,yy,heights,record);
            }
        }
    }
};