Problem

Given anm x nmatrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

初始的思路

• 遍历每一个矩阵的点， 从该点出发，看是否达到Pacific 以及 Atlantic
• 这样子每个点都需要两次的bfs或者dfs
• 不同于number of islands， 这里不需要达到某个点

正确思路

• 实际上上述思路会大大增加时间复杂度，因为会有很多路径是多余和浪费的
• 翻转思路， 我们以及有符合要求的点了， 那么从这些点出发，所能到达的其他点是便是会符合要求的。
• 分别记录这些点

正确思路一（bfs）

    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<>();
        if(matrix == null || matrix.length == 0) return res;

        Queue<int[]> pqueue = new LinkedList<>();
        Queue<int[]> aqueue = new LinkedList<>();

        int m = matrix.length;
        int n = matrix[0].length;

        boolean[][] pGet = new boolean[m][n];
        boolean[][] aGet = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            pqueue.offer(new int[]{i, 0});
            aqueue.offer(new int[]{i, n - 1});
            pGet[i][0] = true;
            aGet[i][n - 1] = true;
        }
        for (int i = 0; i < n; i++) {
            pqueue.offer(new int[]{0, i});
            aqueue.offer(new int[]{m - 1, i});
            pGet[0][i] = true;
            aGet[m - 1][i] = true;
        }

        bfs(matrix, pqueue, pGet);
        bfs(matrix, aqueue, aGet);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pGet[i][j] && aGet[i][j]) {
                    res.add(new int[]{i, j});
                }
            }
        }
        return res;
    }

    private void bfs(int[][] matrix, Queue<int[]> queue, boolean[][] visited) {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while (!queue.isEmpty()) {
            int[] curt = queue.poll();
            for (int i = 0; i < 4; i++) {
                int[] next = new int[]{curt[0] + dx[i], curt[1] + dy[i]};
                if (next[0] < 0 || next[1] < 0 || next[0] >= matrix.length || next[1] >= matrix[0].length || visited[next[0]][next[1]] || matrix[next[0]][next[1]] < matrix[curt[0]][curt[1]]) {
                    continue;
                }
                visited[next[0]][next[1]] = true;
                queue.offer(next);
            }
        }
    }

正确思路二（dfs）

    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<>();
        if(matrix == null || matrix.length == 0) return res;

        int m = matrix.length;
        int n = matrix[0].length;

        boolean[][] pGet = new boolean[m][n];
        boolean[][] aGet = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            pGet[i][0] = true;
            aGet[i][n - 1] = true;
        }
        for (int i = 0; i < n; i++) {
            pGet[0][i] = true;
            aGet[m - 1][i] = true;
        }

        for (int i = 0; i < m; i++) {
            dfs(i, 0, matrix, pGet);
            dfs(i, n - 1, matrix, aGet);
            // dfs(i, 0, matrix, pGet, Integer.MIN_VALUE);
            // dfs(i, n - 1, matrix, aGet, Integer.MIN_VALUE);
        }

        for (int i = 0; i < n; i++) {
            dfs(0, i, matrix, pGet);
            dfs(m - 1, i, matrix, aGet);
            // dfs(0, i, matrix, pGet, Integer.MIN_VALUE);
            // dfs(m - 1, i, matrix, aGet, Integer.MIN_VALUE);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pGet[i][j] && aGet[i][j]) {
                    res.add(new int[]{i, j});
                }
            }
        }
        return res;
    }

    private int[] dx = {1, -1, 0, 0};
    private int[] dy = {0, 0, 1, -1};

    public void dfs(int x, int y, int[][]matrix, boolean[][]visited, int height){
        int n = matrix.length, m = matrix[0].length;
        if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
            return;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            dfs(x+dx[i], y+dy[i], matrix, visited, matrix[x][y]);
        }
    }

    private void dfs(int x, int y, int[][] matrix, boolean[][] visited) {
        for (int i = 0; i < 4; i++) {
            int[] next = new int[]{x + dx[i], y + dy[i]};
            if (next[0] < 0 || next[1] < 0 || next[0] >= matrix.length || next[1] >= matrix[0].length || visited[next[0]][next[1]] || matrix[next[0]][next[1]] < matrix[x][y]) continue;
            visited[next[0]][next[1]] = true;
            dfs(next[0], next[1], matrix, visited);
        }
    }