搜索算法

695、岛屿的最大面积

此题是十分标准的搜索题，我们可以拿来练手深度优先搜索。一般来说，深度优先搜索类型 的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果 可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        maxArea = 0
        m, n = len(grid), len(grid[0])

        for i, l in enumerate(grid):
            for j, s in enumerate(l):
                if grid[i][j]:
                    maxArea = max(self.dfs(grid, i, j), maxArea)
        return maxArea

    def dfs(self, grid, m, n):
        if grid[m][n] == 0:
            return 0
        area = 1
        grid[m][n] = 0
        for i, j in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
            a = m + i
            b = n + j
            if a >= 0 and b >= 0 and a < len(grid) and b < len(grid[0]):
                area += self.dfs(grid, a, b)
        return area

547、省份数量

一样使用深度优先搜索

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(x):
            for i in range(len(isConnected)):
                if isConnected[x][i] == 1 and i not in visited:
                    visited.add(i)
                    dfs(i)

        n = len(isConnected)
        visited = set()
        ans = 0
        for i in range(n):
            if i not in visited:
                dfs(i)
                ans += 1

        return ans

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

雨水的流动方向是从高到低，每个单元格上的雨水只能流到高度小于等于当前单元格的相邻单元格。从一个单元格开始，通过搜索的方法模拟雨水的流动，则可以判断雨水是否可以从该单元格流向海洋。

如果直接以每个单元格作为起点模拟雨水的流动，则会重复遍历每个单元格，导致时间复杂度过高。为了降低时间复杂度，可以从矩阵的边界开始反向搜索寻找雨水流向边界的单元格，反向搜索时，每次只能移动到高度相同或更大的单元格。

由于矩阵的左边界和上边界是太平洋，矩阵的右边界和下边界是大西洋，因此从矩阵的左边界和上边界开始反向搜索即可找到雨水流向太平洋的单元格，从矩阵的右边界和下边界开始反向搜索即可找到雨水流向大西洋的单元格。

可以使用深度优先搜索实现反向搜索，搜索过程中需要记录每个单元格是否可以从太平洋反向到达以及是否可以从大西洋反向到达。反向搜索结束之后，遍历每个网格，如果一个网格既可以从太平洋反向到达也可以从大西洋反向到达，则该网格满足太平洋和大西洋都可以到达，将该网格添加到答案中。

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])

        def search(ocean):
            res = set()

            def dfs(x, y):
                if (x, y) not in res:
                    res.add((x, y))
                    for i, j in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
                        a = x + i
                        b = y + j
                        if a >= 0 and b >= 0 and a < m and b < n and heights[a][b] >= heights[x][y]:
                            dfs(a, b)

            for (i, j) in ocean:
                dfs(i, j)
            return res
            

        pacificOcean = [(0, i) for i in range(n)] + [(i, 0) for i in range(m)]
        atlanticOcean = [(i, n - 1) for i in range(m)] + [(m - 1, i) for i in range(n)]
        
        return list(map(list, search(pacificOcean) & search(atlanticOcean)))