417. 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.

Example 1:

Input: heights = [[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]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

The problem asks every cell that has an "ability" to flow its water into both oceans, not a specific water path. Hope this helps anyone understanding the description and saves your time.

Solution:

DFS:

class Solution {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int row;
    int col;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        row = heights.length;
        col = heights[0].length;

        boolean[][] pacific = new boolean[row][col];
        boolean[][] atlantic = new boolean[row][col];


        for (int i = 0; i < row; i++){
            dfs(heights, pacific, Integer.MIN_VALUE, i, 0);
            dfs(heights, atlantic, Integer.MIN_VALUE, i, col - 1);
        }

        for (int j = 0; j < col; j++){
            dfs(heights, pacific, Integer.MIN_VALUE, 0, j);
            dfs(heights, atlantic, Integer.MIN_VALUE, row - 1, j);
        }

        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (pacific[i][j] == true && atlantic[i][j] == true){
                    result.add(Arrays.asList(i, j));
                }
            }
        }

        return result;


    }

    private void dfs(int[][] heights, boolean[][] visited, int height, int x, int y){

        if (x < 0 || x >= row || y < 0 || y >= col || visited[x][y] == true || height > heights[x][y]){
            return;
        }

        visited[x][y] = true;

        dfs(heights, visited, heights[x][y], x + 1, y);
        dfs(heights, visited, heights[x][y], x - 1, y);
        dfs(heights, visited, heights[x][y], x, y + 1);
        dfs(heights, visited, heights[x][y], x, y - 1);




    }
}
//TC: O(n*m) //  O(4mn)=O(mn) since a cell can be visited at most 4 times.
//SC: O(n*m)

BFS:

class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{0, 1}, {1,0}, {-1,0}, {0, -1}};
    private int numRows;
    private int numCols;
    private int[][] landHeights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        // Check if input is empty
        if (heights.length == 0 || heights[0].length == 0){
            return result;
        }

        // Save initial values to parameters
        numRows = heights.length;
        numCols = heights[0].length;
        landHeights = heights;

        // Setup each queue with cells adjacnet to their respective ocean
        Queue<int[]> pacificQueue = new LinkedList<>();
        Queue<int[]> atlanticQueue = new LinkedList<>();

        for (int i = 0; i < numRows; i++){
            pacificQueue.offer(new int[]{i, 0});
            atlanticQueue.offer(new int[]{i, numCols - 1});
        }

        for (int j = 0; j < numCols; j++){
            pacificQueue.offer(new int[]{0, j});
            atlanticQueue.offer(new int[]{numRows - 1, j});
        }

        // Perform a BFS for each ocean to find all cells accessible 
        // by each ocean
        boolean[][] pacificReachable = bfs(pacificQueue);
        boolean[][] atlanticReachable = bfs(atlanticQueue);

        // Find all cells that can reach both oceans
        for (int i = 0; i < numRows; i++){
            for (int j = 0; j < numCols; j++){
                if (pacificReachable[i][j] == true && atlanticReachable[i][j] == true){
                    result.add(Arrays.asList(i, j));
                }
            }
        }

        return result;
    }

    private boolean[][] bfs(Queue<int[]> queue){
        boolean[][] reachable = new boolean[numRows][numCols];

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            //  This cur is reachable, so mark it
            reachable[cur[0]][cur[1]] = true;
            for (int[] dir : DIRECTIONS){ // Check all 4 directions
                int newRow = cur[0] + dir[0];
                int newCol = cur[1] + dir[1];


                // Check if new cur is within bounds
                if (newRow < 0 || newRow >= numRows || newCol < 0 || newCol >= numCols){
                    continue;
                }

                // Check that the new cur hasn't already been visited
                if (reachable[newRow][newCol]){
                    continue;
                }

                // Check that the new cur has a higher or equal height
                // So that water can flow from the new cur to the old cur
                if (landHeights[newRow][newCol] < landHeights[cur[0]][cur[1]]){
                    continue;
                }
              //  " So that water can flow from the new cur to the old cur " 
              // 这边reachable的 cur是说新的node能否留到我这个旧的node 地方
              // 思维需要反过来下!!!            

                // if we've gotten this far, that means the new cur is reachable
              // add to the if curr height > parent height.
                queue.offer(new int[]{newRow, newCol});
            }
        }

        return reachable;

    }
}
// Time complexity: O(M⋅N), where M is the number of rows and N is the number of columns.
// Space complexity: O(M⋅N), where M is the number of rows and N is the number of columns.

Note

这个reachable的意思是 (除了边界的上的点, 在初始化的时候已经加入queue, 并且在循环过程中会变成reachable == true) 对方海域中的水是否有可能流入当前的node的可能, 可能就是true, 否则false. 当有两张reachable的时候,同时可能的,就是交界处的点, 即答案所要