• 【日常系列】LeetCode《19·BFS 和 DFS》

    数据规模->时间复杂度

    <=10^4 😮(n^2)
    <=10^7:o(nlogn)
    <=10^8:o(n)
    10^8<=:o(logn),o(1)

    内容

    在这里插入图片描述

    lc 589 ：N 叉树的前序遍历
    https://leetcode.cn/problems/n-ary-tree-preorder-traversal/
    提示：
    节点总数在范围 [0, 104]内
    0 <= Node.val <= 104
    n 叉树的高度小于或等于 1000
    进阶：
    递归法很简单，你可以使用迭代法完成此题吗?

    #方案一：迭代
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:return []
        #
        res=[]
        stack=list()
        stack.append(root)
        while stack:
            curr=stack.pop()
            res.append(curr.val)
            #key
            for i in range(len(curr.children)-1,-1,-1):
                stack.append(curr.children[i])
        #
        return res
#方案二：递归
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:return []
        #
        res=[]
        self.dfs(root,res)
        return res
    
    def dfs(self,node,res):
        if not node:return
        res.append(node.val)
        #key
        for children in node.children:
            self.dfs(children,res)
        # for i in range(len(node.children)):
        #     self.dfs(node.children[i],res)

    • 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

    lc 590 ：N 叉树的后序遍历
    https://leetcode.cn/problems/n-ary-tree-postorder-traversal/
    提示：
    节点总数在范围 [0, 104] 内
    0 <= Node.val <= 104
    n 叉树的高度小于或等于 1000
    进阶：
    递归法很简单，你可以使用迭代法完成此题吗?

    #方案一：迭代
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:return []
        res=list()
        stack=[] #list()
        stack.append(root)
        
        while stack:
            curr=stack.pop()
            res.append(curr.val)
            #
            for childnode in curr.children:
                stack.append(childnode) #key
        res.reverse()
        return res
        
#方案二：递归
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        res=[]
        self.dfs(root,res)
        return res

    def dfs(self,node,res):
        if not node:return
        #
        for child in node.children:
            self.dfs(child,res)
        res.append(node.val)

    • 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

    lc 429 ：N 叉树的层序遍历
    https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
    提示：
    树的高度不会超过 1000
    树的节点总数在 [0, 10^4] 之间

    #方案一：BFS
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:return []
        res=[]
        queue=deque()
        queue.append(root)
        while queue:
            level_nodes_val=[]
            for i in range(len(queue)):
                curr=queue.popleft()
                level_nodes_val.append(curr.val) #key
                for child in curr.children:
                    queue.append(child)
            res.append(level_nodes_val)
        return res

#方案二：DFS
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        res=[]
        self.dfs(root,0,res)
        return res
    
    def dfs(self,node,currlevel,res):
        if not node:return []
        #key
        if len(res)-1 <currlevel:
            res.append([node.val])
        else:
            res[currlevel].append(node.val)
        #
        for child in node.children:
            self.dfs(child,currlevel+1,res)

    • 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

    lc 690 ：员工的重要性
    https://leetcode.cn/problems/employee-importance/
    提示：
    一个员工最多有一个 直系 领导，但是可以有多个 直系 下属
    员工数量不超过 2000 。
    在这里插入图片描述

    #方案一：DFS-前序
"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        self.id_map={emp.id:emp for emp in employees} #key:id-emp
        self.total=0 #key
        self.dfs(id)
        return self.total
    
    def dfs(self,id):
        emp=self.id_map[id]
        if not emp:return
        #
        self.total+=emp.importance
        #
        for sub_emp_id in emp.subordinates:
            self.dfs(sub_emp_id)

#方案二：DFS-后序
"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        self.id_map={emp.id:emp for emp in employees} #key:id-emp
        return self.dfs(id)
    
    def dfs(self,id):
        emp=self.id_map[id]
        if not emp:return 0
        #dfs的时候（self.total=0）先累加子节点值，最后在加根节点（root.importance）
        self.total=0  #key:注意位置，
        for sub_emp_id in emp.subordinates:
            self.total+=self.dfs(sub_emp_id) 
            
        return emp.importance+self.total


#方案三：BFS
"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        self.id_map={emp.id:emp for emp in employees} #key:id-emp
        return self.bfs(id)
    
    def bfs(self,id):
        emp=self.id_map[id]
        if not emp:return 0
        #
        res=0
        queue=deque()
        queue.append(emp)
        while queue:
            levelres=0
            for i in range(len(queue)):
                curr=queue.popleft()
                levelres+=curr.importance
                for sub_id in curr.subordinates:
                    queue.append(self.id_map[sub_id]) #key
            res+=levelres
        return res

    • 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
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83

    图的 DFS 和 BFS:key-遍历过程中，设置节点访问

    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    floodfill 算法基础

    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    #数组二维转一维
#数组一维转二维度
#二维数组的四联通
#二维数组的八联通
#保证索引访问合法

    • 1
    • 2
    • 3
    • 4
    • 5

    lc 733 ：图像渲染
    https://leetcode.cn/problems/flood-fill/
    提示:
    m == image.length
    n == image[i].length
    1 <= m, n <= 50
    0 <= image[i][j], newColor < 216
    0 <= sr < m
    0 <= sc < n
    在这里插入图片描述

    #方案一:DFS
class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        self.image=image
        self.visited=[[False]*len(self.image[0]) for _ in range(len(self.image))]
        self.oldcolor=self.image[sr][sc]
        
        self.dfs(sr,sc,color)
        return image
    
    def inarea(self,row,col):
        return row>=0 and row<len(self.image) and col>=0 and col<len(self.image[0])
    
    def dfs(self,row,col,newcolor):
        #终止条件
        if not self.inarea(row,col) or self.image[row][col]!=self.oldcolor:
            return
        #
        self.image[row][col]=newcolor
        self.visited[row][col]=True
        for dir in self.dirs: 
            next_row=row+dir[0]
            next_col=col+dir[1]
            if self.inarea(next_row,next_col):
                if not self.visited[next_row][next_col]: 
                    self.dfs(next_row,next_col,newcolor)
#方案二：BFS
class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        self.image=image
        self.old_color=image[sr][sc]
        if self.old_color == color:  #key
            return image

        self.dirs=[[0,1],[0,-1],[1,0],[-1,0]]
        self.bfs(sr,sc,color)
        return self.image
    
    def inarea(self,row,col):
        return row>=0 and row<len(self.image) and col>=0 and col<len(self.image[0])

    def bfs(self,row,col,newcolor): 
        queue=deque()
        queue.append([row,col])
        self.image[row][col]=newcolor
        while queue:
            curr=queue.popleft()
            #
            for dir in self.dirs: #key1
                nextrow=dir[0]+curr[0]
                nextcol=dir[1]+curr[1]
                if self.inarea(nextrow,nextcol) and self.image[nextrow][nextcol]==self.old_color:
                    queue.append([nextrow,nextcol]) #key1
                    self.image[nextrow][nextcol]=newcolor

    • 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

    lc 463 ：岛屿的周长
    https://leetcode.cn/problems/island-perimeter/
    提示：
    row == grid.length
    col == grid[i].length
    1 <= row, col <= 100
    grid[i][j] 为 0 或 1
    岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连（只有一个岛）
    在这里插入图片描述在这里插入图片描述

    #方案一：DFS-前序
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        self.grid=grid
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        self.visited=[[False]*len(grid[0]) for _ in range(len(grid))]
        #
        self.ans=0
        for i in range(len(self.grid)):
            for j in range(len(self.grid[0])):
                if self.grid[i][j]==1:
                    self.dfs(i,j)
                    return self.ans
    
    def inarea(self,row,col):
        return row>=0 and row<len(self.grid) and col>=0 and col<len(self.grid[0])

    def dfs(self,row,col):
        if not self.inarea(row,col) or self.grid[row][col]==0 or self.visited[row][col]:
            return
        #
        self.visited[row][col]=True
        for dir in self.dirs:
            nextrow=dir[0]+row
            nextcol=dir[1]+col
            #key:计边长
            if not self.inarea(nextrow,nextcol) or self.grid[nextrow][nextcol]==0:
                self.ans+=1
            elif not self.visited[nextrow][nextcol]:
                self.dfs(nextrow,nextcol)
            
#方案二：DFS-后序
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        self.grid=grid
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        self.visited=[[False]*len(grid[0]) for _ in range(len(grid))]
        #
        for i in range(len(self.grid)):
            for j in range(len(self.grid[0])):
                if self.grid[i][j]==1:
                    return self.dfs(i,j)
    
    def inarea(self,row,col):
        return row>=0 and row<len(self.grid) and col>=0 and col<len(self.grid[0])

    def dfs(self,row,col):
        if not self.inarea(row,col) or self.grid[row][col]==0:
            return 1
        if self.visited[row][col]:
            return 0  #说明接壤
        #
        ans=0
        self.visited[row][col]=True
        for dir in self.dirs:
            nextrow=dir[0]+row
            nextcol=dir[1]+col
            ans+=self.dfs(nextrow,nextcol) #key:基于'四边'情况统计
        return ans  #对比lc690

#方案三：BFS
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        self.grid=grid
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        self.visited=[[False]*len(grid[0]) for _ in range(len(grid))]
        #
        for i in range(len(self.grid)):
            for j in range(len(self.grid[0])):
                if self.grid[i][j]==1:
                    return self.bfs(i,j)
    
    def inarea(self,row,col):
        return row>=0 and row<len(self.grid) and col>=0 and col<len(self.grid[0])

    def bfs(self,row,col):
        queue=deque()
        queue.append([row,col])
        self.visited[row][col]=True
        #
        ans=0
        while queue:
            curr=queue.popleft()
            for dir in self.dirs:
                nextrow=curr[0]+dir[0]
                nextcol=curr[1]+dir[1]
                if not self.inarea(nextrow,nextcol) or self.grid[nextrow][nextcol]==0:
                    ans+=1
                elif not self.visited[nextrow][nextcol]: #key
                    queue.append([nextrow,nextcol])
                    self.visited[nextrow][nextcol]=True
        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
    • 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
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92

    lc 200 ：岛屿数量【top100】
    https://leetcode.cn/problems/number-of-islands/
    提示：
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 300
    grid[i][j] 的值为 ‘0’ 或 ‘1’

    #DFS：
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid=grid
        self.rows=len(grid)
        self.cols=len(grid[0])
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        self.visited=[[False]*self.cols for _ in range(self.rows)]
        #
        ans=0
        for i in range(self.rows):
            for j in range(self.cols):
                if self.grid[i][j]=="1" and not self.visited[i][j]:
                    self.dfs(i,j)
                    ans+=1
        #
        return ans

    def inarea(self,row,col):
        return self.rows>row>=0 and self.cols>col>=0

    def dfs(self,row,col):
        if not self.inarea(row,col) or self.grid[row][col]=='0' or self.visited[row][col]:
            return
        self.visited[row][col]=True
        for dir in self.dirs:
            nextrow=row+dir[0]
            nextcol=col+dir[1]
            self.dfs(row,col)


    • 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

    lc 695 ：岛屿的最大面积
    https://leetcode.cn/problems/max-area-of-island/
    提示：
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 50
    grid[i][j] 为 0 或 1
    在这里插入图片描述

    #DFS-后序：
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        self.grid=grid
        self.rows=len(grid)
        self.cols=len(grid[0])
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        self.visited=[[False]*self.cols for _ in range(self.rows)]
        #
        maxans=0
        for i in range(self.rows):
            for j in range(self.cols):
                if self.grid[i][j]==1 and not self.visited[i][j]:
                    maxans=max(self.dfs(i,j),maxans)
        #
        return maxans

    def inarea(self,row,col):
        return self.rows>row>=0 and self.cols>col>=0

    def dfs(self,row,col):
        if not self.inarea(row,col) or self.grid[row][col]==0 or self.visited[row][col]:#key:递归中接壤也是0
            return 0
        #
        self.visited[row][col]=True
        ans=0
        for dir in self.dirs:
            nextrow=row+dir[0]
            nextcol=col+dir[1]
            ans+=self.dfs(nextrow,nextcol)
        return 1+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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    lc 130 ：被围绕的区域
    https://leetcode.cn/problems/surrounded-regions/
    提示：
    m == board.length
    n == board[i].length
    1 <= m, n <= 200
    board[i][j] 为 ‘X’ 或 ‘O’
    在这里插入图片描述

    class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.rows=len(board)
        self.cols=len(board[0])
        self.board=board
        self.visited=[[False]*self.cols for _ in range(self.rows)]
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        #边界
        for j in range(self.cols):
            if self.board[0][j]=='O' and not self.visited[0][j]:self.dfs(0,j)
            if self.board[self.rows-1][j]=='O' and not self.visited[self.rows-1][j]:self.dfs(self.rows-1,j)
        for i in range(1,self.rows-1):
            if self.board[i][0]=='O' and not self.visited[i][0]:self.dfs(i,0)
            if self.board[i][self.cols-1]=='O' and not self.visited[i][self.cols-1]:self.dfs(i,self.cols-1)
        #替换
        for i in range(self.rows):
            for j in range(self.cols):
                if self.board[i][j]=='O' and not self.visited[i][j]:
                    self.board[i][j]='X'
        
    def area(self,row,col):
        return 0<=row<self.rows and 0<=col<self.cols
    def dfs(self,row,col):
        if not self.area(row,col) or self.board[row][col]=='X' or self.visited[row][col]:
            return 
        #
        self.visited[row][col]=True
        for dir in self.dirs:
            nextrow=row+dir[0]
            nextcol=col+dir[1]
            self.dfs(nextrow,nextcol)  

    • 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

    lc 1034 ：边框着色
    https://leetcode.cn/problems/coloring-a-border/
    提示：
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 50
    1 <= grid[i][j], color <= 1000
    0 <= row < m
    0 <= col < n
    在这里插入图片描述
    在这里插入图片描述

    class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        #
        self.color=color
        self.currcolor=grid[row][col]
        if grid[row][col]==color:return grid
        #
        self.rows=len(grid)
        self.cols=len(grid[0])
        self.grid=grid
        self.visited=[[False]*self.cols for _ in range(self.rows)]
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1]]
        self.dfs(row,col)
        return self.grid
    
    
    def area(self,row,col):
        return 0<=row<self.rows and 0<=col<self.cols
    def dfs(self,row,col):
        if not self.area(row,col) or self.grid[row][col]!=self.currcolor or self.visited[row][col]:
            return 
        #通过(nextrow,nextcol)对当前顶点判定及递归
        self.visited[row][col]=True
        for dir in self.dirs:
            nextrow=row+dir[0]
            nextcol=col+dir[1]
            #key条件
            if not self.area(nextrow,nextcol) or (self.grid[nextrow][nextcol]!=self.currcolor and not self.visited[nextrow][nextcol]):
                self.grid[row][col]=self.color #key-not [nextrow][nextcol]
            #
            self.dfs(nextrow,nextcol)

    • 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

    lc 529 ：扫雷游戏
    https://leetcode.cn/problems/minesweeper/
    提示：
    m == board.length
    n == board[i].length
    1 <= m, n <= 50
    board[i][j] 为 ‘M’、‘E’、‘B’ 或数字 ‘1’ 到 ‘8’ 中的一个
    click.length == 2
    0 <= clickr < m
    0 <= clickc < n
    board[clickr][clickc] 为 ‘M’ 或 ‘E’
    注：E:未挖空 B：已挖空 M：未挖雷 X：已挖雷
    在这里插入图片描述

    class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        self.rows=len(board)
        self.cols=len(board[0])
        self.board=board
        self.visited=[[False]*self.cols for _ in range(self.rows)]
        self.dirs=[[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]]
        #
        if board[click[0]][click[1]]=='M':#如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'
            board[click[0]][click[1]]='X'
        else:
            self.dfs(click[0],click[1])
        return board
        
    def area(self,row,col):
        return 0<=row<self.rows and 0<=col<self.cols
    
    def dfs(self,row,col):
        if not self.area(row,col) or self.board[row][col]!='E' or self.visited[row][col]:
            return 
        #统计雷数
        m_s=0
        for dir in self.dirs:
            nextrow=row+dir[0]
            nextcol=col+dir[1]
            if self.area(nextrow,nextcol) and self.board[nextrow][nextcol]=='M':
                m_s+=1
        #更新board
        #key:雷区是没有必要再递归的
        if m_s>0:
            self.board[row][col]=str(m_s)#如果一个 至少与一个地雷相邻 的空方块（'E'）被挖出，修改它为数字（'1' 到 '8' ），表示相邻地雷的数量。
        else:
            self.board[row][col]='B'
            #key位置：如果一个 没有相邻地雷 的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
            for dir in self.dirs:
                nextrow=row+dir[0]
                nextcol=col+dir[1]
                self.dfs(nextrow,nextcol)

    • 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

    lc 994 ：腐烂的橘子
    https://leetcode.cn/problems/rotting-oranges/
    提示：
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 10
    grid[i][j] 仅为 0、1 或 2
    每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
    在这里插入图片描述

    #多源BFS
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        self.dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        self.rows, self.cols = len(grid), len(grid[0])
        self.grid=grid
        #多源
        queue=deque()
        for i in range(self.rows):
            for j in range(self.cols):
                if grid[i][j]==2:
                    queue.append([i,j])
        #
        ans=-1
        while queue:
            for i in range(len(queue)):
                curr=queue.popleft()
                #
                for dir in self.dirs:
                    nextrow,nextcol=curr[0]+dir[0],curr[1]+dir[1]
                    #key
                    if self.area(nextrow,nextcol) and self.grid[nextrow][nextcol]==1:
                        self.grid[nextrow][nextcol]=2
                        queue.append([nextrow,nextcol])
            ans+=1
        #
        for i in range(self.rows):
            for j in range(self.cols):
                if self.grid[i][j]==1:
                    return -1
        return max(ans,0) #[[0]]
    
    
    def area(self,row,col):
        return 0<=row<self.rows and 0<=col<self.cols 

    • 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
  • 相关阅读:
    vue3 setup语法糖
    v4l2-ioctl.c的一些学习和整理
    2023年高校大数据实验室建设及大数据实训平台整体解决方案
    springboot实验室自主预约系统毕业设计源码111953
    HIVE内置函数hash() -- 源码解析
    uCOSii中的事件标志组
    Windows安装kafka 2.13-2.7.0
    JVM各种情况内存溢出分析
    TornadoFx的TableView组件使用
    应对数字化挑战职场人真的要学python吗？
  • 原文地址：https://blog.csdn.net/qq_42889517/article/details/127467462