个人技术分享

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

思路

代码

(1) MyMothed

// 符合条件的点 : 既可以到达左或上边界，也可以到达右或下边界；
class Solution {
private:
    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    vector<vector<int>> result; 
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y)
    {
        int i, j;
        int next_x, next_y;
        int m = heights.size(), n = heights[0].size();
        for(i = 0; i < 4; i++)
        {
            next_x = x + dir[i][0];
            next_y = y + dir[i][1];
            
            if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n)
            {
                continue;
            }
            if(!visited[next_x][next_y] && heights[next_x][next_y] <= heights[x][y])
            {   
                visited[next_x][next_y] = true;
                dfs(heights, visited, next_x, next_y);
            }
        }
    }

public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int i, j;
        int m = heights.size(), n = heights[0].size();
        vector<vector<bool>> visited_P(m, vector<bool>(n, false)); // Pacific Ocean
        vector<vector<bool>> visited_A(m, vector<bool>(n, false)); // Atlantic Ocean
        result.clear();
        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                heights[i][j] = -heights[i][j];
            }
        }

        // Pacific
        i = 0;
        for(j = 0; j < n; j++)
        {
            if(!visited_P[i][j])
            {
                visited_P[i][j] = true;
                dfs(heights, visited_P, i, j);
            }
        }
        j = 0;
        for(i = 0; i < m; i++)
        {
            if(!visited_P[i][j])
            {
                visited_P[i][j] = true;
                dfs(heights, visited_P, i, j);
            }
        }

        // Atlantic
        i = m-1;
        for(j = 0; j < n; j++)
        {
            if(!visited_A[i][j])
            {
                visited_A[i][j] = true;
                dfs(heights, visited_A, i, j);
            }
        }
        j = n-1;
        for(i = 0; i < m; i++)
        {
            if(!visited_A[i][j])
            {
                visited_A[i][j] = true;
                dfs(heights, visited_A, i, j);
            }
        }
        cout << "P" << endl;
        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                cout << visited_P[i][j] << ", ";
            }
            cout << endl;
        }
        cout << "A" << endl;
        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                cout << visited_A[i][j] << ", ";
            }
            cout << endl;
        }
        // 能重合的地方就是想要的点
        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                if(visited_P[i][j] && visited_A[i][j])
                {
                    result.push_back({i, j});
                }
            }
        }
        return result;
    }
};

把海拔翻转一下，分别统计从太平洋能流经的地盘和大西洋能流经的地盘，这两个地盘的重合部分就是题目所求；