###### tags: `Leetcode` `medium` `array` `dfs` `bfs` `python` `c++`

# 417. Pacific Atlantic Water Flow

## [題目連結:] https://leetcode.com/problems/pacific-atlantic-water-flow/

## 題目:
There is an ```m x n``` rectangular island that borders both the **Pacific Ocean** and **Atlantic Ocean**. The **Pacific Ocean** touches the island's left and top edges, and the **Atlantic Ocean** touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an ```m x n``` integer matrix ```heights``` where ```heights[r][c]``` represents the **height above sea level** of the cell at coordinate ```(r, c)```.

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is **less than or equal to** the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a **2D list** of grid coordinates ```result``` where ```result[i] = [ri, ci]``` denotes that rain water can flow from cell ```(ri, ci)``` to **both** the Pacific and Atlantic oceans.


## 解題想法:
* 此題為給一matrix，左邊與上面代表太平洋(Pacific Ocean)、右邊與下面代表大西洋(Atlantic Ocean)
* 水往低處流，求哪些位置的水能同時流入兩個洋
* 想法:
* 已知水往低處流
* 逆向思考: **假設海水漲潮時，水能漲到陸地最高點**
* 小->大
* 則分別從左上紀錄太平洋vs右下紀錄大西洋，水能達到的最高位置
* 取兩者重疊處即為解

## Python_Sol1: DFS

class Solution(object):
    def pacificAtlantic(self, heights):
        """
        :type heights: List[List[int]]
        :rtype: List[List[int]]
        """
        #水往低處流
        #逆向思考: 設海水漲潮時，水能漲到陸地最高點
        #分別左上紀錄太平洋vs右下紀錄大西洋 水能達到位置
        #取重疊處
        m=len(heights)
        n=len(heights[0])
        if m==0 or n==0:
            return []
        Pvisited=[ [False for _ in range(n)] for _ in range(m)]
        Avisited=[ [False for _ in range(n)] for _ in range(m)]
        #邊界
        for i in range(m):
            self.dfs(heights,i,0,Pvisited,0) #左: P太平洋
            self.dfs(heights,i,n-1,Avisited,0) #右: A大西洋
        for j in range(n):
            self.dfs(heights,0,j,Pvisited,0) #上: P太平洋
            self.dfs(heights,m-1,j,Avisited,0) #下: A大西洋
        #取交集
        res=[]
        for i in range(m):
            for j in range(n):
                #取皆為True的: 表示皆能到達的位置
                if Pvisited[i][j] and Avisited[i][j]:
                    res.append([i,j])
        return res
    
    def dfs(self, heights, i, j, visited, preMin):
        #若當前位置不符合邊界or已經訪問過or當前位置的高度比preMin還小: 則return 
        m=len(heights)
        n=len(heights[0])
        if  i>=m or i<0 or j>=n or j<0 or visited[i][j] or heights[i][j]<preMin:
            return 
        #否則代表可以流到達
        visited[i][j]=True
        #遞迴四個方向, 比較位置preMin換成當前的height[i][j]
        self.dfs(heights,i+1,j,visited,heights[i][j])
        self.dfs(heights,i-1,j,visited,heights[i][j])
        self.dfs(heights,i,j+1,visited,heights[i][j])
        self.dfs(heights,i,j-1,visited,heights[i][j])

## Python_Sol2: BFS

class Solution(object):
    def pacificAtlantic(self, heights):
        """
        :type heights: List[List[int]]
        :rtype: List[List[int]]
        """
        #水往低處流
        #逆向思考: 設海水漲潮時，水能漲到陸地最高點
        #分別左上紀錄太平洋vs右下紀錄大西洋 水能達到位置
        #取重疊處
        m=len(heights)
        n=len(heights[0])
        if m==0 or n==0:
            return []
        Pvisited=[ [False for _ in range(n)] for _ in range(m)]
        Avisited=[ [False for _ in range(n)] for _ in range(m)]
        #邊界
        for i in range(m):
            self.bfs(heights,i,0,Pvisited) #左: P太平洋
            self.bfs(heights,i,n-1,Avisited) #右: A大西洋
        for j in range(n):
            self.bfs(heights,0,j,Pvisited) #上: P太平洋
            self.bfs(heights,m-1,j,Avisited) #下: A大西洋
        #取交集
        res=[]
        for i in range(m):
            for j in range(n):
                #取皆為True的: 表示皆能到達的位置
                if Pvisited[i][j] and Avisited[i][j]:
                    res.append([i,j])
        return res
    
    def bfs(self, heights, i, j, visited):
        m=len(heights)
        n=len(heights[0])
        que=[(i,j)]
        dirs=[(1,0), (-1,0), (0,1), (0,-1)]
        while que:
            curx,cury=que.pop()
            visited[curx][cury]=True
            #遍歷四周
            for dirx, diry in dirs:
                tmpx=curx+dirx
                tmpy=cury+diry
                #檢查是否出界 且 鄰居值要更大
                if (0<=tmpx<m and 0<=tmpy<n and heights[curx][cury]<=heights[tmpx][tmpy]):
                    #且還沒訪問過
                    if not visited[tmpx][tmpy]:
                        que.append((tmpx,tmpy))
        return 

## C++_Sol1: DFS

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m=heights.size(), n=heights[0].size();
        if (m==0 || n==0)
            return {};
        vector<vector<bool>> Pvisited(m,vector<bool>(n, false));
        vector<vector<bool>> Avisited(m,vector<bool>(n, false));
        //right, left
        for (int i=0; i<m; i++){
            dfs(heights, i, 0, Pvisited, 0);
            dfs(heights, i, n-1, Avisited, 0);
        }
        //top, bottom
        for (int j=0; j<n; j++){
            dfs(heights, 0, j, Pvisited, 0);
            dfs(heights, m-1, j, Avisited, 0);
        }
        vector<vector<int>> res;
        //intersection
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (Pvisited[i][j] && Avisited[i][j])
                    res.push_back({i,j});
            }
        }
        return res;
    }

    void dfs(vector<vector<int>>& heights, int i ,int j, vector<vector<bool>>& visited, int preMin){
        int m=heights.size(), n=heights[0].size();
        //Check if it's legal
        if (i>=m || i<0 || j>=n || j<0 || visited[i][j] || heights[i][j]<preMin )
            return;
        visited[i][j]=true;
        //dfs neighber
        dfs(heights, i+1, j, visited, heights[i][j]);
        dfs(heights, i-1, j, visited, heights[i][j]);
        dfs(heights, i, j+1, visited, heights[i][j]);
        dfs(heights, i, j-1, visited, heights[i][j]);
    }
};

## C++_Sol2: BFS
* 先存邊界於queue中，再逐一遍歷

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m=heights.size(), n=heights[0].size();
        if (m==0 || n==0)
            return {};
        vector<vector<bool>> Pvisited(m,vector<bool>(n, false));
        vector<vector<bool>> Avisited(m,vector<bool>(n, false));
        queue<pair<int,int>> Pque, Aque;
        //right, left
        for (int i=0; i<m; i++){
            Pque.push({i,0});
            Pvisited[i][0]=true;
            Aque.push({i,n-1});
            Avisited[i][n-1]=true;
        }
        //top, bottom
        for (int j=0; j<n; j++){
            Pque.push({0,j});
            Pvisited[0][j]=true;
            Aque.push({m-1,j});
            Avisited[m-1][j]=true;
        }
        bfs(heights, Pvisited, Pque);
        bfs(heights, Avisited, Aque);
        vector<vector<int>> res;
        //intersection
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (Pvisited[i][j] && Avisited[i][j])
                    res.push_back({i,j});
            }
        }
        return res;
    }

    void bfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, queue<pair<int, int>>& que){
        int m=heights.size(), n=heights[0].size();
        vector<vector<int>> dirs{{1,0}, {-1,0}, {0,1}, {0,-1}};
        while (!que.empty()){
            auto cur=que.front(); que.pop();
            visited[cur.first][cur.second]=true;
            //check neighber 
            for (auto dir: dirs){
                int tmpx=dir[0]+cur.first;
                int tmpy=dir[1]+cur.second;
                if (tmpx>=m || tmpx<0 || tmpy>=n || tmpy<0 || visited[tmpx][tmpy] || heights[cur.first][cur.second]>heights[tmpx][tmpy])
                    continue;
                que.push({tmpx, tmpy});
            }
        } 
    }
};