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

题目描述

  题目链接,417. 太平洋大西洋水流问题,题目截图如下:

image-20220427180206849

image-20220427180228146 image-20220427180240183

题目分析

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

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

  而在遍历的时候就是我们通用的深度优先遍历的方法了,定义方向数组,枚举起点,然后每次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);
            }
        }
    }
};

结语

  我要一步一步往上爬,在最高点乘着叶片往前飞~

Q.E.D.


  Java后端开发工程师一名,北漂一族,欢迎大家前来交流