深度优先搜索|1034, 1020, 1254

边界着色

把这个题分段了，先找到包括 (row, col) 的连通分量，然后再去找符合条件的边界，找到以后涂上颜色就行。

class Solution:def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:m = len(grid)n = len(grid[0])def dfs(i,j):#print(i,j)con[i][j] = Truefor k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:if (0 <= k1 < m and 0 <= k2 < n) and grid[k1][k2] == grid[i][j] and not con[k1][k2]:dfs(k1,k2)def diff(i,j):for k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:if (0 <= k1 < m and 0 <= k2 < n) and grid[k1][k2] != grid[i][j]:return Truereturn Falsecon = [[False]*n for _ in range(m)]dfs(row,col)for i in range(m):for j in range(n):if not con[i][j]: continue if i == 0 or i == m-1 or j == 0 or j == n-1: continueif not diff(i,j): con[i][j] = Falsefor i in range(m):for j in range(n):if con[i][j]: grid[i][j] = colorreturn grid

机器人的运动范围

这个类型的题也算比较熟悉了，也是看能走到哪一步，不能走的地方拦一下。

class Solution:def movingCount(self, m: int, n: int, k: int) -> int:def num_sum(i,j):a = str(i)+str(j)s = 0for i in a:s += int(i)return sres = 0used = [[False]*n for _ in range(m)]def dfs(i,j,k):nonlocal resres += 1used[i][j] = Truefor k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:if (0 <= k1 < m and 0 <= k2 < n) and num_sum(k1,k2) <= k and not used[k1][k2]:dfs(k1,k2,k)dfs(0,0,k)return res

扫雷问题

这个题逻辑上没有什么问题，但有两个问题要注意：

• 第一点是如果初始点不是炸弹的话，其实不会踩上去的，所以这个结局应该是翻到没有可以翻了就结束，所以下面的判断是写在dfs外面的不是里面

if board[click[0]][click[1]] == 'M':board[click[0]][click[1]] = 'X'return board

class Solution:def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:direc = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[-1,1],[-1,-1],[1,-1]]m = len(board)n = len(board[0])if board[click[0]][click[1]] == 'M':board[click[0]][click[1]] = 'X'return boarddef empty(i,j):boom = 0for k1,k2 in direc:x = i+k1y = j+k2if (0<=x<m and 0<=y<n) and board[x][y] == 'M':boom += 1return boomdef dfs(i,j):     num_b = empty(i,j)if not num_b:board[i][j] = 'B'for k1,k2 in direc:x = i+k1y = j+k2if 0<=x<m and 0<=y<n and board[x][y]=='E':dfs(x,y)else:board[i][j] = str(num_b)dfs(click[0],click[1])return board

• 一开始一直内存不够，本来以为是方向的问题，后来发现是没有剪枝。在进入递归之前是需要判断是不是等于’E’的，因为之前走过的’E’已经’B’了，所以如果不说明的话会反复横跳，然后超出范围。

if 0<=k1<m and 0<=k2<n and board[k1][k2]=='E':dfs(k1,k2)

class Solution:def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:#direc = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[-1,1],[-1,-1],[1,-1]]m = len(board)n = len(board[0])def empty(i,j):boom = 0for k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1],[i+1,j+1],[i-1,j+1],[i-1,j-1],[i+1,j-1]]:if (0<=k1<m and 0<=k2<n) and board[k1][k2] == 'M':boom += 1return boomdef dfs(i,j):   if board[click[0]][click[1]] == 'M':board[click[0]][click[1]] = 'X'returnnum_b = empty(i,j)if not num_b:board[i][j] = 'B'for k1,k2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1],[i+1,j+1],[i-1,j+1],[i-1,j-1],[i+1,j-1]]:if 0<=k1<m and 0<=k2<n and board[k1][k2]=='E':dfs(k1,k2)else:board[i][j] = str(num_b)dfs(click[0],click[1])return board