Leecode DFS深度优先搜索

定义

图解
深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

网格类问题的 DFS 遍历方法

网格问题的基本概念

我们首先明确一下岛屿问题中的网格结构是如何定义的，以方便我们后面的讨论。

网格问题是由 m * n 个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，
要在这样的网格上进行某种搜索。

岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子，
数字为 1 的格子看成陆地格子，这样相邻的陆地格子就连接成一个岛屿。	

在这样一个设定下，就出现了各种岛屿问题的变种，包括岛屿的数量、面积、周长等。不过这些问题，
基本都可以用 DFS 遍历来解决。
1
2
3
4
5
6
7
8
9
10

994. 腐烂的橘子

解答

"""
1、首先分别将腐烂的橘子和新鲜的橘子保存在两个集合中；
2、模拟广度优先搜索的过程，方法是判断在每个腐烂橘子的四个方向上是否有新鲜橘子，如果有就腐烂它。每腐烂一次时间加 +1，并剔除新鲜集合里腐烂的橘子；
3、当橘子全部腐烂时结束循环。
"""
# 整洁版
class Solution:
    def orangesRotting(self, grid):
        row = len(grid)
        col = len(grid[0])
        rotten = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2}  # 腐烂集合
        fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}  # 新鲜集合
        time = 0
        while fresh:
            if not rotten: return -1
            rotten = {(i + di, j + dj) for i, j in rotten for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)] if
                      (i + di, j + dj) in fresh}  # 即将腐烂的如果在新鲜的集合中，就将它腐烂
            fresh -= rotten  # 剔除腐烂的
            time += 1
        return time


# 描述版
class Solution:
    def orangesRotting(self, grid):
        #  腐烂橘子集合、新鲜橘子集合
        fresh, rotten = set(), set()
        n, m = len(grid), len(grid[0])
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    rotten.add((i, j))
                elif grid[i][j] == 1:
                    fresh.add((i, j))

        time = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        # 遍历腐烂橘子集合，向各个方位腐烂新鲜的橘子 
        while fresh:
            if not rotten:
                return -1

            # 即将腐烂的如果在新鲜的集合中，就将它腐烂
            temp_rotten = set()
            for i, j in directions:
                for di, dj in rotten:
                    if (di + i, dj + j) in fresh:
                        temp_rotten.add((di + i, dj + j))

            rotten = temp_rotten
            # 将新鲜的橘子腐烂
            fresh -= temp_rotten
            time += 1

        return time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

463. 岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
1

示例 1：
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边
1
2
3
4

解答

class Solution:
    def islandPerimeter(self, grid):
        n, m = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] != 1:
                    continue
                ans += 4
                for di, dj in directions:
                    temp_i = di + i
                    temp_j = dj + j
                    # 判断新的坐标有没有越界，并且是否又相连的区域；
                    if all([temp_i >= 0, temp_i <= n - 1, temp_j >= 0, temp_j <= m - 1, grid[temp_i][temp_j] == 1]):
                        ans -= 1

        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
1
2
3
4

解答

"""
 1、获取网格的边界
 2、遍历边界，把相连的并且为O的位置进行转换为*
 3、还原，把*转换为O，其他的转换为#
"""

class Solution:
    def solve(self, board):

        def dfs(i, j):
            if board[i][j] == "O":
                board[i][j] = "*"
                for di, dj in directions:
                    tempi, tempj = di + i, dj + j
                    # 判断边界
                    if tempi >= 0 and tempi <= n - 1 and tempj >= 0 and tempj <= m - 1:
                        dfs(tempi, tempj)

        n, m = len(board), len(board[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        # 获取边界,由边界向里面寻找
        res = set()
        for j in range(m):
            dfs(0, j)
            dfs(n - 1, j)

        for i in range(n):
            dfs(i, 0)
            dfs(i, m - 1)

        for i in range(n):
            for j in range(m):
                board[i][j] = "O" if board[i][j] == "*" else "X"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
1
2
3
4

解答

"""
思路和上一题一样，不过本次需要递归统计每次查找的数量。
"""
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            # 判断边界
            if not (i >= 0 and i <= n - 1 and j >= 0 and j <= m - 1 and grid[i][j] == 1):
                return 0

            num, grid[i][j] = 1, 0
            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                tempi, tempj = di + i, dj + j
                num += dfs(tempi, tempj)

            return num

        n, m, ans = len(grid), len(grid[0]), 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    ans = max(ans, dfs(i, j))

        return ans
                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25