DAY22: LeetCode 733：图像渲染——从二维网格开始理解 DFS 和 BFS

LeetCode 733图像渲染 Flood Fill——从二维网格开始理解 DFS 和 BFS目录LeetCode 733图像渲染 Flood Fill——从二维网格开始理解 DFS 和 BFS一、准备做 200可以先做这道题二、先理解二维网格中的“四个方向”1、怎么保证四个方向一个都不会漏2、首先要记住起点原来的颜色3、还要判断有没有越界三、先不管 DFS 和 BFS这道题到底应该怎么想1、先处理起点2、检查当前格子的四个邻居3、进入 (0,1) 以后怎么办4、还要解决一个问题不能一直走回来方法一二维布尔数组方法二使用 set 保存坐标5、一个特殊情况新颜色和原颜色一样四、方法一DFS1、为什么这里可以使用递归2、DFS 大概是怎么走的3、DFS 完整代码五、方法二BFS1、为什么要使用队列2、初始化队列3、popleft() 是什么意思4、为什么找到邻居以后要加入队列5、为什么加入队列之前就要修改颜色DFSBFS6、BFS 完整代码六、DFS 和 BFS 到底是什么关系1、DFS一条路先走深2、BFS一层一层往外扩3、用同一张图来看区别七、复杂度1、DFS 的空间复杂度2、BFS 的空间复杂度八、这道题要学啥第一二维网格其实也可以理解成“点和点之间的连接”第二要有 visited 的意识第三DFS 和 BFS 的核心问题其实一样一、准备做 200可以先做这道题LeetCode 733图像渲染我原本准备做 LeetCode 200「岛屿数量」但刚开始接触二维网格搜索时对“从一个点向四周搜索”这件事还不是特别熟悉。所以可以先做 733。这道题可以帮助理解一个非常重要的模型从一个起点开始把所有和它上下左右连通并且数值相同的格子全部找出来。这个模型其实就是后面 200「岛屿数量」的基础。733 已经直接告诉了我们从哪里开始我们只需要解决怎么从这个起点出发 把和它连起来的一整块区域全部找出来而 200 则是在这个基础上再增加一步自己去寻找每一座岛的起点二、先理解二维网格中的“四个方向”刚开始我以为从初始点出发分别往上、下、左、右一直遍历。但实际上并不是沿着四条直线一直扫。假设当前格子的坐标是(row, col)那么它紧挨着的四个格子分别是上(row - 1, col) 下(row 1, col) 左(row, col - 1) 右(row, col 1)也就是说我们每一次只检查当前格子周围的一格。如果某个相邻格子符合要求就进入这个格子然后再从这个新格子继续检查它自己的上、下、左、右。例如1 1 0 0 1 1 0 0 1从左上角(0,0)开始可以一路找到(0,0) → (0,1) ↓ (1,1) → (1,2) ↓ (2,2)所以真正的思路是每到达一个新的格子都重新检查它自己的四个邻居。1、怎么保证四个方向一个都不会漏可以先把四个方向统一保存下来directions[(-1,0),# 上(1,0),# 下(0,-1),# 左(0,1)# 右]之后每到达一个格子就执行fordr,dcindirections:new_rowrowdr new_colcoldc例如当前在(row, col)四轮循环分别会得到row - 1, col row 1, col row, col - 1 row, col 1所以可以把dr dc理解成这一轮行和列分别要变化多少例如(-1, 0)表示行 -1 列不变也就是向上移动一格。只要每一个到达的格子都执行一次这个for它的四个方向就不会漏掉。2、首先要记住起点原来的颜色题目要求修改的是与初始位置上下左右连通并且和初始位置颜色相同的格子。所以最开始应该先保存起点原来的颜色originalimage[sr][sc]例如image[sr][sc] 1那么original 1之后我们寻找邻居时就可以判断image[new_row][new_col]original只有颜色仍然等于起点原来的颜色才属于我们需要继续寻找的区域。3、还要判断有没有越界二维数组不是无限大的。假设rowslen(image)colslen(image[0])分别表示rows 总行数 cols 总列数那么合法坐标必须满足0new_rowrows0new_colcols为什么是这样比如总共有 3 行第 0 行 第 1 行 第 2 行合法行下标其实就是0 ~ rows - 1所以写成0new_rowrows列也是同样的道理。PS: 这里判断的是整张图像的边界三、先不管 DFS 和 BFS这道题到底应该怎么想现在已经知道当前格子 → 有上、下、左、右四个邻居但真正的问题是从起点(sr, sc)开始怎么把所有和它连通、并且颜色相同的格子全部找出来假设1 1 0 0 1 1 0 0 1起点是(0,0)起点颜色是1所以我们的目标就是从 (0,0) 出发 通过上下左右移动 把所有能够到达的 1 找出来1、先处理起点起点本身肯定属于需要修改的区域。假设新颜色是2那么可以先把(0,0)修改成2 1 0 0 1 1 0 0 1现在(0,0)已经处理好了。接下来应该干什么自然就是检查它周围有没有其他和它连在一起的12、检查当前格子的四个邻居当前位置(0,0)它的四个邻居是上(-1,0) 下(1,0) 左(0,-1) 右(0,1)但不是每个位置都可以进入。一个邻居至少要满足1. 没有越界 2. 颜色还是 original这里上(-1,0) → 越界 左(0,-1) → 越界 下(1,0) → 颜色是 0 右(0,1) → 颜色是 1所以真正能够继续进入的是(0,1)3、进入(0,1)以后怎么办来到(0,1)以后问题又变成了(0,1)周围还有没有和它连通的1也就是说我们又要做一模一样的事情处理当前格子 ↓ 检查四个方向 ↓ 找到符合条件的邻居 ↓ 进入邻居 ↓ 再检查邻居自己的四周例如可能形成(0,0) ↓ (0,1) ↓ (1,1) ↓ (1,2) ↓ (2,2)这时候会发现一个很重要的特点每进入一个新格子我们面对的其实还是同一个问题。都是处理当前格子 寻找它符合要求的邻居 继续处理邻居而这种“一个大问题里面又出现了完全相同的小问题”的结构就非常适合递归。4、还要解决一个问题不能一直走回来例如有两个相邻的格子A BA 可以走到 B。但是来到 B 以后B 左边又是 A。如果完全不记录哪些格子已经处理过就可能出现A → B → A → B → A...一直来回走。所以一个格子访问以后必须留下一个我已经处理过的标记。这道题其实正好可以利用“修改颜色”来做这件事。例如original 1 color 2访问一个格子以后1 → 2之后我们只允许进入image[new_row][new_col]original已经变成2的格子自然不会再次满足2 1所以修改颜色不仅完成了题目的要求同时也相当于给这个格子做了 visited 标记。不过通常情况下如果题目不能直接修改原网格就会额外准备一个visited来记录哪些格子已经访问过。最常见有两种写法。方法一二维布尔数组假设rowslen(image)colslen(image[0])可以创建visited[[False]*colsfor_inrange(rows)]一开始所有位置都是False表示还没有访问过例如False False False False False False False False False如果现在访问了(0,1)就可以visited[0][1]True变成False True False False False False False False False以后再准备进入一个邻居时除了判断有没有越界以及这个格子本身是否满足题目条件还要多判断notvisited[new_row][new_col]比如if(0new_rowrowsand0new_colcolsandnotvisited[new_row][new_col]andimage[new_row][new_col]original):一旦决定进入这个格子就先visited[new_row][new_col]True表示这个格子已经被发现过了之后不要再重复进入。方法二使用 set 保存坐标也可以写visitedset()访问一个格子以后visited.add((row,col))例如visited.add((0,1))那么visited里面可能保存{(0,0), (0,1), (1,1)}之后判断一个格子有没有访问过(new_row,new_col)notinvisited就可以了。所以一般的网格搜索其实是当前位置 ↓ 检查四个邻居 ↓ 判断有没有越界 ↓ 判断是否满足题目条件 ↓ 判断有没有访问过 ↓ 如果可以进入 ↓ 先标记 visited ↓ 再继续搜索而 733 比较特殊因为image[row][col]color本身就已经能看出这个格子访问过了所以不需要再额外创建visited。可以把两种情况简单记成如果可以安全修改原数组 → 经常直接修改原数组当 visited 如果不能修改原数组 → 单独建立 visited5、一个特殊情况新颜色和原颜色一样假设original 1 color 1那么修改1 → 1其实什么都没有发生。这样“修改颜色作为访问标记”的方法就失效了。例如A → B → A → B...仍然可能不断重复访问。而且既然原颜色 新颜色最终整张图片本来也不会发生任何变化所以可以一开始直接iforiginalcolor:returnimage不用继续搜索。四、方法一DFS前面已经自己推出了这样一个过程进入当前格子 ↓ 处理当前格子 ↓ 检查四个邻居 ↓ 发现符合要求的邻居 ↓ 进入邻居 ↓ 邻居继续做同样的事情这其实就是 DFS。DFSDepth First Search深度优先搜索。可以简单理解成找到一个能继续走的邻居以后马上进入这个邻居然后继续往更深处找。1、为什么这里可以使用递归我们可以写一个函数dfs(row,col)它只负责一件事处理当前位置(row, col)然后寻找它能够继续进入的邻居。进入当前格子以后image[row][col]color然后检查四个方向fordr,dcindirections:new_rowrowdr new_colcoldc如果新的位置① 没有越界 ② 颜色仍然等于 original说明它也是这块连通区域的一部分。那么接下来怎么办其实还是做和当前格子完全一样的事情dfs(new_row,new_col)所以递归并不是突然冒出来的。而是因为处理邻居的问题和处理当前格子的问题完全一样。2、DFS 大概是怎么走的例如1 1 0 0 1 1 0 0 1从(0,0)开始。可能会一路(0,0) → (0,1) → (1,1) → (1,2) → (2,2)DFS 的感觉就是发现能继续走 ↓ 马上进去 ↓ 再发现能继续走 ↓ 继续进去 ↓ 直到这条路走不下去之后递归才会一层一层返回继续检查之前还没有检查完的其他方向。3、DFS 完整代码classSolution:deffloodFill(self,image:list[list[int]],sr:int,sc:int,color:int)-list[list[int]]:originalimage[sr][sc]iforiginalcolor:returnimage rowslen(image)colslen(image[0])directions[(-1,0),(1,0),(0,-1),(0,1)]defdfs(row,col):image[row][col]colorfordr,dcindirections:new_rowrowdr new_colcoldcif(0new_rowrowsand0new_colcolsandimage[new_row][new_col]original):dfs(new_row,new_col)dfs(sr,sc)returnimage整个 DFS 的核心其实就是dfs(当前格子) ↓ 先处理当前格子 ↓ 检查四个方向 ↓ 找到符合要求的邻居 ↓ dfs(邻居)也就是进入一个格子 → 做标记 → 检查四个邻居 → 符合条件就继续进入。五、方法二BFS理解 DFS 以后再来看 BFS 就会自然很多。DFS 的做法是发现一个邻居 ↓ 马上进入这个邻居 ↓ 继续往深处寻找那么我也可以换一种方式发现一个邻居以后我先不马上进去而是先把它记下来等之后再处理。也就是说我们需要一个地方保存已经发现但是还没有检查它四周的格子。这就是 BFS 中的队列queue。1、为什么要使用队列假设当前处理 AA然后发现两个邻居B C我们暂时不马上进入 B 或 C而是先记录待处理 B C之后先处理 B 再处理 C而 B 在处理过程中又可能发现D E那么队列可能变成C D E也就是说先发现的格子先处理。这正好符合队列的先进先出 First In First Out(FIFO)队列正常使用需要fromcollectionsimportdeque2、初始化队列queuedeque([(sr,sc)])其中(sr,sc)表示一个坐标。例如(1, 2)表示第 1 行第 2 列外面的[(sr,sc)]表示一个列表作用是把这个坐标作为一个整体放进 deque 里。因为 deque() 接收的是一个可以遍历的对象。如果直接写deque((sr, sc))那么 (sr, sc) 会被拆开变成sr sc 两个元素。而我们希望队列里保存的是(sr, sc) 这样一个完整的坐标所以外面需要再套一层列表。3、popleft()是什么意思BFS 每次从队列最前面取出一个待处理格子row,colqueue.popleft()例如queue [(1,2), (1,3), (2,2)]执行row,colqueue.popleft()会取出(1,2)于是row 1 col 2队列剩下[(1,3), (2,2)]接下来就开始检查(1,2)自己的四个方向。4、为什么找到邻居以后要加入队列假设处理(1,2)时发现(1,3)也是合法邻居。这时候queue.append((1,3))并不是说(1,3) 已经处理完了而是表示我已经发现了(1,3)但还没有检查它自己的四个方向所以先放进待处理队列。因此 BFS 的queue可以理解成已经发现但还没有继续检查四周的格子。5、为什么加入队列之前就要修改颜色BFS 中一般会这样写image[new_row][new_col]color queue.append((new_row,new_col))而不是等这个格子以后被popleft()取出来的时候才修改颜色。原因是一个格子可能同时被多个邻居发现。例如A → C B → CA 先发现 C。如果只是queue.append(C)但是没有立刻给 C 做标记那么之后 B 检查邻居时也会发现C 还是 original于是又会queue.append(C)最终C被重复加入队列。所以正确顺序应该是发现一个合法邻居 ↓ 立即修改颜色表示已经发现过 ↓ 再放进 queue也就是image[new_row][new_col]color queue.append((new_row,new_col))这里可以注意一个区别DFSDFS 中dfs(new_row,new_col)一进入函数就马上image[row][col]color所以访问标记是在“进入 DFS 时”完成。BFSBFS 中邻居不会马上处理而是先进入队列。所以应该在加入队列之前就做好标记防止它在等待处理期间再次被其他格子加入。6、BFS 完整代码fromcollectionsimportdequeclassSolution:deffloodFill(self,image:list[list[int]],sr:int,sc:int,color:int)-list[list[int]]:originalimage[sr][sc]iforiginalcolor:returnimage rowslen(image)colslen(image[0])directions[(-1,0),(1,0),(0,-1),(0,1)]queuedeque([(sr,sc)])image[sr][sc]colorwhilequeue:row,colqueue.popleft()fordr,dcindirections:new_rowrowdr new_colcoldcif(0new_rowrowsand0new_colcolsandimage[new_row][new_col]original):image[new_row][new_col]color queue.append((new_row,new_col))returnimageBFS 的整体过程就是起点放进 queue ↓ 给起点做标记 ↓ 从 queue 取出一个格子 ↓ 检查四个方向 ↓ 发现合法邻居 ↓ 立刻做标记 ↓ 把邻居加入 queue ↓ 继续处理 queue 中剩下的格子六、DFS 和 BFS 到底是什么关系刚开始可能会觉得DFS 做完以后是不是还可以继续优化成 BFS但其实不是。DFS 和 BFS 并不是普通方法 ↓ 优化方法而是两种不同的搜索顺序。它们解决的都是从一个起点出发 把能够到达的所有位置找出来区别主要在于下一步先处理谁1、DFS一条路先走深DFS发现邻居 ↓ 马上进入邻居 ↓ 继续寻找邻居 ↓ 一条路一直往深处走递归 DFS 实际上借助的是函数调用栈所以可以简单记成DFS → stack / 递归调用栈 → 一条路先走深2、BFS一层一层往外扩BFS发现邻居 ↓ 先放进 queue ↓ 先把当前附近的格子处理掉 ↓ 再继续往外扩散它使用的是队列 queue所以可以记成BFS → queue → 一层一层往外扩3、用同一张图来看区别例如A / \ B C / \ D EDFS 可能是A → B → D → 回到 B → E → 回到 A → C因为找到一条路以后先一直走深而 BFS 更像A → B、C → D、E先处理离 A 一步的再处理离 A 两步的。所以DFS 和 BFS 找到的连通区域可能完全一样只是访问顺序不同。七、复杂度假设图像大小为rows × cols也就是一共有rows × cols个格子。最坏情况下整张图所有格子都和起点连通。那么每个格子最多被真正访问一次。所以 DFS 和 BFS 的时间复杂度都是O(rows × cols)1、DFS 的空间复杂度递归 DFS 需要使用函数调用栈。如果连通区域特别大最坏情况下递归深度也可能达到rows × cols所以空间复杂度最坏为O(rows × cols)2、BFS 的空间复杂度BFS 需要使用queue最坏情况下队列中也可能同时保存大量格子。所以最坏空间复杂度同样为O(rows × cols)因此在这道题里BFS 并不是 DFS 的时间复杂度优化版本。两者主要只是搜索方式不同。不过 Python 中递归 DFS 如果连通区域特别大有可能因为递归层数过深出现RecursionError这种情况下可以考虑BFS或者自己使用 stack 写迭代 DFS避免依赖 Python 的递归调用栈。八、这道题要学啥真正需要建立的是一个二维网格搜索模型从一个起点开始 ↓ 处理当前格子 ↓ 检查上、下、左、右 ↓ 判断有没有越界 ↓ 判断这个邻居能不能进入 ↓ 能进入就做访问标记 ↓ 继续从这个邻居向四周搜索也就是从一个点出发把与它连通的一整块区域全部找出来。这里还有几个非常重要的思想。第一二维网格其实也可以理解成“点和点之间的连接”每一个格子都可以看成一个点。如果两个格子上下左右相邻并且满足题目的移动条件就可以认为两个点之间可以连接所以 DFS 和 BFS 并不只是“树的算法”。二维网格同样可以使用。第二要有 visited 的意识搜索过程中最容易出现的问题就是A → B → A → B...所以必须有办法判断这个位置我是不是已经处理过了733 比较特殊可以直接用修改颜色代替visited以后其他题不一定能修改原数组就可能需要单独写visitedset()或者visited[[False]*colsfor_inrange(rows)]第三DFS 和 BFS 的核心问题其实一样它们都在解决从当前点还能到哪里真正不同的是DFS发现以后马上处理 BFS发现以后先存起来之后按照队列顺序处理