题目

难度：★★★☆☆
类型：二维数组
方法：深度优先搜索

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

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

提示：

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

示例

给定下面的 5x5 矩阵:

太平洋 ~ ~ ~ ~ ~
~ 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 *
* * * * * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

解答

方格问题常常可以使用深度优先搜索实现。这个问题我们最好采用逆向思维，俗话说，水往低处流，能够流向太平洋和大西洋的点，恐怕是最后被两大洋淹没的，例如电影2012中的珠峰。问题就转化成了，如果世界末日来临，海水上涨，哪些点是可以被最后淹没的。这里为了便于大家理解，把点方格和大陆都做了实例化。

相关实例和方法：
【点】：获取点的位置，获取相邻的点；
【方格】：获取方格中某点的值，设置方格中某点的值，判断点是否在方格内；
【大陆】：包含三个主要的实例变量，即每个点的海拔，先被太平洋淹没的点的网格和先被大西洋淹没的点的网格，我们称为太平洋占领区和大西洋占领区，后面的两个方格，是布尔类型的，用于表示太平洋或大西洋上涨后哪些点会被淹没掉，暂且认为太平洋和大西洋是分隔开的。

如何进行深度优先搜索？首先我们应该搞清楚在本任务中深度优先搜索的意义在哪里。以太平洋为例，海水上涨后，海拔低的点是要优先被淹没的，海水从海陆边界那些点出发，开始蔓延到内陆，每当淹没一个点之后，就需要考察该点周围的四个点的海拔与当前点的海拔之间的关系，如果高于获得等于当前点，则继续淹没，否则停止淹没，这样保证水流是一直向上的，才能找到山顶。

深度优先搜索完成后，面对左上角一堆True的太平洋占领区和右下角一堆True的大西洋占领区，如何确定山顶的坐标？其实两个方格对应位置做与就可以了，这些点也就可以满足，水流既可以到太平洋，也可以到大西洋。

class Point:
    """
    点的实例，包含获取左边、右边、上边、下边相邻点和获取当前坐标值的方法。
    """
    def __init__(self, h, w):
        self.h = h
        self.w = w

    @property
    def left(self):
        return Point(self.h, self.w-1)

    @property
    def right(self):
        return Point(self.h, self.w+1)

    @property
    def upper(self):
        return Point(self.h-1, self.w)

    @property
    def lower(self):
        return Point(self.h+1, self.w)

    @property
    def locate(self):
        return [self.h, self.w]


class Board:
    """
    网格实例，用于构建网格，包含取某点值，设置某点值，判断点是否在网格内等方法。
    """
    def __init__(self, value):

        value = value if value else [[]]
        self.value = value
        self.height = len(value)
        self.width = len(value[0])

    def get(self, point):
        assert isinstance(point, Point)
        if self.is_valid(point):
            return self.value[point.h][point.w]
        return -1

    def set(self, point, value):
        assert isinstance(point, Point)
        if self.is_valid(point):
            self.value[point.h][point.w] = value
            return True
        return -1

    def is_valid(self, point):
        assert isinstance(point, Point)
        return 0 <= point.w < self.width and 0 <= point.h < self.height


class MainLand:
    """
    陆地实例。包含淹没太平洋，淹没大西洋，获取山顶坐标等方法。
    """
    def __init__(self, value):

        self.land = Board(value)
        self.width = self.land.width
        self.height = self.land.height
        self.pacific = Board([[False for _ in range(self.width)] for _ in range(self.height)])      # 太平洋淹没的陆地
        self.atlantic = Board([[False for _ in range(self.width)] for _ in range(self.height)])     # 大西洋淹没的陆地

    def submerge_atlantic(self, point):
        """
        太平洋淹没该陆地
        :param point:
        :return:
        """
        assert isinstance(point, Point)
        self.atlantic.set(point, True)

        def submerge(p):
            if self.atlantic.get(p) is False and self.land.get(p) >= self.land.get(point):
                self.submerge_atlantic(p)

        submerge(point.left)
        submerge(point.right)
        submerge(point.upper)
        submerge(point.lower)

    def submerge_pacific(self, point):
        """
        大西洋淹没该陆地
        :param point:
        :return:
        """
        assert isinstance(point, Point)
        self.pacific.set(point, True)

        def submerge(p):
            if self.pacific.get(p) is False and self.land.get(p) >= self.land.get(point):
                self.submerge_pacific(p)

        submerge(point.left)
        submerge(point.right)
        submerge(point.upper)
        submerge(point.lower)

    def submerge_all(self):

        pacific_boarders = [Point(0, j) for j in range(self.width)] + [Point(i, 0) for i in range(self.height)]
        atlantic_boarders = [Point(self.height-1, j) for j in range(self.width)] + [Point(i, self.width-1) for i in range(self.height)]

        for p in pacific_boarders:
            self.submerge_pacific(p)

        for p in atlantic_boarders:
            self.submerge_atlantic(p)

    @property
    def get_peak(self):
        """
        根据太平洋和大西洋淹没的陆地交集，获得山顶坐标。
        :return:
        """
        results = []
        for i in range(self.height):
            for j in range(self.width):
                point = Point(i, j)
                if self.pacific.get(point) and self.atlantic.get(point):
                    results.append(point.locate)
        return results


class Solution:
    def pacificAtlantic(self, matrix):
        mainland = MainLand(matrix)
        mainland.submerge_all()
        # return mainland.
        peak_list = mainland.get_peak
        return peak_list


if __name__ == "__main__":
    matrix = [[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],
              ]
    s = Solution()
    res = s.pacificAtlantic(matrix)
    print(res)

以题目为例，海拔方格，太平洋占领区和大西洋占领区分别为：

海拔：
[[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],
]
太平洋占领区：
[[True, True, True, True, True],
 [True, True, True, True, True],
 [True, True, True, False, False],
 [True, True, False, False, False],
 [True, False, False, False, False]]
大西洋占领区：
[[False, False, False, False, True],
 [False, False, False, True, True],
 [False, False, True, True, True],
 [True, True, True, True, True],
 [True, True, True, True, True]]

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析