417. Pacific Atlantic Water Flow

T: O(4*mn + mn)

S: O(2*mn)

class Solution {
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        
        int m = heights.length;
        int n = heights[0].length;
        boolean pacific[][] = new boolean[m][n];
        boolean atlantic[][] = new boolean[m][n];

        for (int j = 0; j < n; j++) {
            pacific[0][j] = true;
            dfs(heights, 0, j, pacific);
            
            atlantic[m-1][j] = true;
            dfs(heights, m-1, j, atlantic);
        }
        for (int i = 0; i < m; i++) {
            pacific[i][0] = true;
            dfs(heights, i, 0, pacific);
            
            atlantic[i][n-1] = true;
            dfs(heights, i, n-1, atlantic);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }
        }
        return res;
        
    }
    private void dfs(int[][] heights, int i, int j, boolean visited[][]) {
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            
            if (!inArea(heights, x, y) || visited[x][y] || heights[i][j] > heights[x][y]) { // new should higer than before
                continue;
            }
            visited[x][y] = true;
            dfs(heights, x, y, visited);
        }
    }
    private boolean inArea(int[][] heights, int i, int j) {
        return i >= 0 && i < heights.length && j >= 0 && j < heights[0].length;
    }
}

/*
Pacific Ocean touches the island's left and top edges
and the Atlantic Ocean touches the island's right and bottom edges.

heights[r][c]

water flow:
curr cell height >= neightbor height

    P

P       A
    A

return result[i] = [ri, ci] => [[ri, ci],[ri, ci],[ri, ci]...]
rain water can flow from cell (ri, ci) to 
both the Pacific and Atlantic oceans.


water flow: 思路是從低處到高處做, 水往高處流...反正能相通兩邊就好了
curr cell height >= neightbor height => 
如果從邊邊出發, 這條件就要相反 => curr cell height <= neightbor

反過來就是 curr cell height > neightbor, 不繼續

Pacific
dfs from i = 0, j = 0~n-1
dfs from i = 0~m-1, j = 0
if (water can arrive, Pacific[i][j] = true)

Atlantic
dfs from i = m-1, j = 0~n-1
dfs from i = 0~m-1, j = n-1
if (water can arrive, Atlantic[i][j] = true)


at last for (i 0~m)
          for (j 0~n)
        if water both can arrive, put to res[]
        

ps.
对于一个点它能流动两边的大洋，那么反过来，两边大洋的水反着流就能达到这个点。
尽然水开始倒流了，那么逻辑也需要反过来，因此只有将下一个点比当前的点大时或者等于当前点的高度时，水才能流过去。


*/