想让网站的文章都被收录怎么做,做网站需要的照片,国外平面设计欣赏网站,域名注册商深度优先搜索|1034. 边界着色#xff0c; 机器人的运动范围#xff0c;529. 扫雷游戏 边界着色机器人的运动范围扫雷问题 边界着色
把这个题分段了#xff0c;先找到包括 (row, col) 的连通分量#xff0c;然后再去找符合条件的边界#xff0c;找到以后涂上颜色就行。
c… 深度优先搜索|1034. 边界着色 机器人的运动范围529. 扫雷游戏 边界着色机器人的运动范围扫雷问题 边界着色
把这个题分段了先找到包括 (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 [[i1,j],[i-1,j],[i,j1],[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 [[i1,j],[i-1,j],[i,j1],[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 [[i1,j],[i-1,j],[i,j1],[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]] Xreturn boardclass 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]] Xreturn boarddef empty(i,j):boom 0for k1,k2 in direc:x ik1y jk2if (0xm and 0yn) and board[x][y] M:boom 1return boomdef dfs(i,j): num_b empty(i,j)if not num_b:board[i][j] Bfor k1,k2 in direc:x ik1y jk2if 0xm and 0yn 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 0k1m and 0k2n 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 [[i1,j],[i-1,j],[i,j1],[i,j-1],[i1,j1],[i-1,j1],[i-1,j-1],[i1,j-1]]:if (0k1m and 0k2n) and board[k1][k2] M:boom 1return boomdef dfs(i,j): if board[click[0]][click[1]] M:board[click[0]][click[1]] Xreturnnum_b empty(i,j)if not num_b:board[i][j] Bfor k1,k2 in [[i1,j],[i-1,j],[i,j1],[i,j-1],[i1,j1],[i-1,j1],[i-1,j-1],[i1,j-1]]:if 0k1m and 0k2n and board[k1][k2]E:dfs(k1,k2)else:board[i][j] str(num_b)dfs(click[0],click[1])return board
