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

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要
m 和 n 都小于150

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.*;

class Solution {

    private final int[][] direactions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private boolean greater(int[][] heights, int x1, int y1, int x2, int y2) {
        if (x2 < 0 || x2 >= heights.length || y2 < 0 || y2 >= heights[0].length) {
            return true;
        }
        return heights[x1][y1] >= heights[x2][y2];
    }

    public List> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;

        Set visited1 = new HashSet<>();
        Queue queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            Point point = new Point(-1, i);
            queue.offer(point);
        }

        for (int i = 0; i < m; ++i) {
            Point point = new Point(i, -1);
            queue.offer(point);
        }

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < direactions.length; ++i) {
                int x = point.x + direactions[i][0];
                int y = point.y + direactions[i][1];
                Point next = new Point(x, y);
                if (x >= 0 && x < m && y >= 0 && y < n && greater(heights, x, y, point.x, point.y) && !visited1.contains(next)) {
                    visited1.add(next);
                    queue.offer(next);
                }
            }
        }

        Set visited2 = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            Point point = new Point(m, i);
            queue.offer(point);
        }

        for (int i = 0; i < m; ++i) {
            Point point = new Point(i, n);
            queue.offer(point);
        }

        List> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            if (visited1.contains(point)) {
                ans.add(Arrays.asList(point.x, point.y));
            }
            for (int i = 0; i < direactions.length; ++i) {
                int x = point.x + direactions[i][0];
                int y = point.y + direactions[i][1];
                Point next = new Point(x, y);
                if (x >= 0 && x < m && y >= 0 && y < n && greater(heights, x, y, point.x, point.y) && !visited2.contains(next)) {
                    visited2.add(next);
                    queue.offer(next);
                }
            }
        }
        return ans;
    }
}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}