leetcode 417. Pacific Atlantic Water Flow可以到达两边的点+经典DFS深度优先遍历做法

快来打我* 2022-06-04 10:19 110阅读 0赞

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:  
The order of returned grid coordinates does not matter.  
Both m and n are less than 150.  
Example:

Given the following 5x5 matrix:

Pacific ~ ~ ~ ~ ~  
~ 1 2 2 3 (5) \*  
~ 3 2 3 (4) (4) \*  
~ 2 4 (5) 3 1 \*  
~ (6) (7) 1 4 5 \*  
~ (5) 1 1 2 4 \*  
\* \* \* \* \* Atlantic

Return:

\[\[0, 4\], \[1, 3\], \[1, 4\], \[2, 2\], \[3, 0\], \[3, 1\], \[4, 0\]\] (positions with parentheses in above matrix).

这道题看起来很简单，但是一开始搞不清楚这个是什么问题，后来想了很久才明白是什么意识。

首先，水是由高出向低处流动，那么题意的要求就是寻找这样的点，它可以留到太平洋和大西洋，要注意只要矩阵的四边才是太平洋和大西洋，那么我们是要找一个点它可以走到太平洋和大西洋，做法就是一个DFS深度优先遍历，针对每一点做遍历，只要可以走到就可以了，

但是这个题也可以反过来做，也就是水像高处走，那么我们只需要从太平洋和大西洋出发，找到相关点即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& mat) 
        {
            vector<pair<int, int>> res;
            if (mat.size() <= 0)
                return res;
            int row = mat.size(), col = mat[0].size();
            vector<vector<bool>> pacific(row,vector<bool>(col,false));
            vector<vector<bool>> atlantic(row, vector<bool>(col, false));
            for (int i = 0; i < row; i++)
            {
                dfs(mat, pacific,  INT_MIN, i, 0);
                dfs(mat, atlantic, INT_MIN, i, col-1);
            }
    
            for (int i = 0; i < col; i++)
            {
                dfs(mat, pacific, INT_MIN, 0, i);
                dfs(mat, atlantic, INT_MIN, row-1, i);
            }
    
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (pacific[i][j] == true && atlantic[i][j] == true)
                    {
                        res.push_back(make_pair(i,j));
                    }
                }
            }
            return res;
        }
    
    
        void dfs(vector<vector<int>>& mat, vector<vector<bool>>& visit,int pre ,int x,int y)
        {
            int row = mat.size(), col = mat[0].size();
            if (x < 0 || x >= row || y<0 || y >= col || visit[x][y] == true || mat[x][y]<pre)
                return;
            else
            {
                visit[x][y] = true;
                dfs(mat, visit, mat[x][y], x - 1 ,y);
                dfs(mat, visit, mat[x][y], x + 1, y);
                dfs(mat, visit, mat[x][y], x, y - 1);
                dfs(mat, visit, mat[x][y], x, y + 1);
            }
        }
    };