# 0417. Pacific Atlantic Water Flow
###### tags: `Leetcode` `Medium` `DFS` `BFS`
link: https://leetcode.com/problems/pacific-atlantic-water-flow/
## 思路
从海开始做dfs
visited同时也代表能不能到达 所以不能在dfs这个点之前就把它设成visited
## Code

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] pacVisited = new boolean[m][n];
        boolean[][] atlVisited = new boolean[m][n];
        
        for(int i=0; i<m; i++){
            dfs(heights, pacVisited, -1, i, 0);
            dfs(heights, atlVisited, -1, i, n-1);
        }
        for(int i=0; i<n; i++){
            dfs(heights, pacVisited, -1, 0, i);
            dfs(heights, atlVisited, -1, m-1, i);
        }
        
        List<List<Integer>> ans = new ArrayList<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(pacVisited[i][j] && atlVisited[i][j]){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    ans.add(temp);
                }
            }
        }
        return ans;
    }
    
    private void dfs(int[][] heights, boolean[][] visited, int prev, int x, int y){
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        if(x<0 || x>=visited.length || y<0 || y>=visited[0].length || visited[x][y] || prev > heights[x][y]) return;
        visited[x][y] = true;
        for(int[] dir:dirs){
            int nextx = x+dir[0], nexty = y+dir[1];
            dfs(heights, visited, heights[x][y], nextx, nexty);
        }
    }
}