417. 太平洋大西洋水流问题

深度优先搜索

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {

    int m;
    int n;
    int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List> pacificAtlantic(int[][] heights) {

        List> list = new LinkedList<>();

        m = heights.length;
        n = heights[0].length;
        boolean[][] canReachPacific = new boolean[m][n];
        boolean[][] canReachAtlantic = new boolean[m][n];

        /**
         * 类似于《130. 被围绕的区域》的逆向思维
         * 从中间寻找可以同时流到两大洋的数字比较麻烦，但是反过来，从边缘寻找可以逆向流入的数字却比较方便
         * 边缘的第0行和第0列贴近Pacific，所以肯定可以流入；同理第m - 1行和第n - 1列肯定可以流入Atlantic
         */
        for (int i = 0; i < n; i++) {

            dfs(heights, 0, i, canReachPacific);
            dfs(heights, m - 1, i, canReachAtlantic);
        }

        for (int i = 0; i < m; i++) {

            dfs(heights, i, 0, canReachPacific);
            dfs(heights, i, n - 1, canReachAtlantic);
        }

        /**
         * 如果一个数字可以同时被两大洋逆向流入，就记录下坐标
         * Arrays.asList()方法将数组转换为列表
         */
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (canReachAtlantic[i][j] && canReachPacific[i][j]) {
                    list.add(Arrays.asList(i, j));
                }
            }
        }

        return list;
    }

    /**
     * 所有边缘的数字，以及大于等于前一个且没被遍历过的数字，都能被逆向流入相应的大洋
     */
    public void dfs(int[][] heights, int row, int col, boolean[][] canReach){

        canReach[row][col] = true;

        for (int i = 0; i < 4; i++) {

            int newRow = row + move[i][0];
            int newCol = col + move[i][1];

            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !canReach[newRow][newCol] && heights[row][col] <= heights[newRow][newCol]) {
                dfs(heights, newRow, newCol, canReach);
            }
        }
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/pacific-atlantic-water-flow/