LeetCode 200岛屿数量——从 Flood Fill 到二维网格 BFS目录LeetCode 200岛屿数量——从 Flood Fill 到二维网格 BFS一、从 733 图像渲染继续往下做二、一开始我对“岛屿”的理解有点绕三、那怎么知道自己发现了一座新岛1、为什么“没访问过的 1”就是一座新岛2、为什么下一次遇到没访问过的 1一定是新岛四、BFS 和外面的扫描到底怎么配合五、BFS 怎么把一整座岛找出来六、完整代码七、写的时候踩到的一个小坑这里是字符串 1八、为什么这里没有把 0 也加入 visited九、 复杂度十、从 733 到 200又学了什么一、从 733 图像渲染继续往下做LeetCode 200岛屿数量这道题我是接着前面的 733「图像渲染」做的。如果对二维网格中的四方向移动、DFS、BFS 还不是很熟可以先看前一篇LeetCode 733图像渲染 Flood Fill——从二维网格开始理解 DFS 和 BFS733 已经解决了一个很重要的问题给我一个起点怎么从这个起点出发把和它上下左右连通的一整块区域全部找出来例如1 1 0 1 1 0 0 0 1如果从左上角的1开始那么通过 BFS / DFS可以找到1 1 1 1这一整块连在一起的区域。而 200「岛屿数量」其实是在这个基础上多问了一步如果现在连起点都不给我我怎么把地图里的每一座岛都找出来二、一开始我对“岛屿”的理解有点绕题目说岛屿被水包围并且水平方向或竖直方向相邻的陆地可以连接成一座岛。我刚开始就在想岛屿不是应该四周全部都是 0 吗甚至会想到要不要先在整个grid外面补一圈0然后检查一块陆地是不是被0包围其实思考题目的时候确实可以把网格外面想象成一圈海水。例如原本是1 1 0 0 1 0 0 0 1脑子里可以想象成0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0这样比较容易理解边界上的陆地外面同样也是水。但代码里其实没有必要真的给grid补一圈0。因为后面 BFS 检查邻居时本来就会判断0new_rowm0new_coln一旦走出grid就不能继续往外走。所以对于搜索来说走出 grid和遇到外面的海水效果其实是一样的。而且后来我发现如果真的按照“检查一块陆地是不是四周被0包围”这个方向去想反而把问题想复杂了。例如0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0这里有两座岛。左边这座岛是1 1 1 1但显然其中某一个1的四周并不全都是0因为它旁边还有其他陆地。所以“岛屿四周环水”并不是说每一个1四周都是0。真正的想法应该是上下左右连在一起的所有1属于同一座岛。而0的作用就是把不同的岛隔开。例如1 1 0 0 1 1 1 0 1 1左边的1和右边的1中间隔着0。因此从左边开始 BFS也没有办法穿过0到达右边。所以它们自然属于不同的岛。三、那怎么知道自己发现了一座新岛想清楚“岛就是一整块连通的1”以后我还是有一个问题起点在哪里我到底应该从哪里开始 BFS不过这样还是想复杂了。。。其实根本不需要提前找起点。直接按照最普通的顺序扫描整个grid从上到下 从左到右也就是foriinrange(m):forjinrange(n):每次看一个格子。如果是0说明是海水直接继续。如果是1就要再看这个 1 以前有没有访问过这里visited就非常重要了。这个在733哪里详细讲过~ LeetCode 7331、为什么“没访问过的 1”就是一座新岛假设1 1 0 0 0 1 1 0 0 1 0 0 0 1 1从左上角开始扫描。第一次遇到(0,0) 1而且(0,0) 没有 visited那么至少可以确定我发现了一块以前没有处理过的陆地。所以count1先记录发现了一座岛。接下来再从(0,0)开始 BFS把和它连在一起的所有1全部找出来。例如 BFS 最后发现(0,0) (0,1) (1,0) (1,1)那么就把这些位置全部加入visited可以暂时想象成V V 0 0 0 V V 0 0 1 0 0 0 1 1其中V表示已经访问过。这时候再继续扫描。即使后面重新遇到(0,1) (1,0) (1,1)它们虽然原本也是1但已经在visited里面了。所以不会再次count1这就是visited在这道题里最重要的作用一座岛只要被发现一次就通过 BFS 把整座岛全部标记掉之后扫描到同一座岛的其他陆地时就不会重复计数。2、为什么下一次遇到没访问过的1一定是新岛继续扫描V V 0 0 0 V V 0 0 1 0 0 0 1 1中间的0全部跳过。最后又遇到(1,4) 1而且(1,4) not in visited这时候为什么又可以直接这样count1这是因为如果(1,4)和前面的岛连在一起那么前面那一次 BFS 就应该已经顺着上下左右走到这里并把它加入visited。但现在它仍然没有访问过。说明之前那座岛的 BFS 没有办法走到这里中间一定被0隔开了。所以它属于另一座岛。这时候再count 1然后从(1,4)开启新一轮 BFS把第二座岛全部找出来。所以判断新岛的条件其实非常简单grid[i][j]1and(i,j)notinvisited只要满足它是陆地 以前没有被任何一座岛的 BFS 访问过就说明发现了一座新的岛。四、BFS 和外面的扫描到底怎么配合这里我一开始还有一个地方比较绕。因为 BFS 会从一个1开始不断检查它的上、下、左、右然后继续往外扩。那我就在想一座岛 BFS 完以后我怎么重新开始从左到右、从上到下扫描其实根本不用“重新开始”。因为这里实际上有两层不同的工作。外面的双循环foriinrange(m):forjinrange(n):负责寻找下一座还没有发现的岛。而里面的 BFS 负责一旦发现一座岛就把这一整座岛全部找完。也就是说双循环扫描到一个格子 ↓ 发现是 1而且没访问过 ↓ count 1 ↓ 暂时进入 BFS ↓ BFS 把这整座岛全部 visited ↓ BFS 结束 ↓ 回到原来的双循环 ↓ 继续扫描后面的格子例如双循环扫描到(0,0)在这里启动了一次 BFS。BFS 完成以后并不会让双循环消失。程序还是会回来继续扫描(0,1) (0,2) (0,3) ...只不过(0,1)如果属于刚刚那座岛现在已经visited了所以直接跳过。这样两者的职责就很清楚了双循环 → 找每一座岛的第一个“未访问陆地” BFS → 从这一块陆地出发把整座岛全部找出来这其实就是从 733 到 200 最大的变化。733 是题目直接把起点给我 ↓ 我只需要 BFS 一次200 是自己扫描寻找起点 ↓ 每发现一座新岛 ↓ 启动一次 BFS五、BFS 怎么把一整座岛找出来这一部分其实和 733 已经非常接近了。假设已经发现(i, j)是一个新的、没有访问过的1。首先visited.add((i,j))然后把它作为 BFS 的起点queuedeque([(i,j)])之后不断从队列取出一个格子row,colqueue.popleft()检查它的四个方向directions[(-1,0),(1,0),(0,-1),(0,1)]对于每一个邻居需要满足1. 没有越界 2. 是陆地 1 3. 还没有访问过也就是if(0new_rowmand0new_colnandgrid[new_row][new_col]1and(new_row,new_col)notinvisited):满足以后visited.add((new_row,new_col))queue.append((new_row,new_col))这里还是和 733 一样发现一个合法邻居以后先标记 visited再加入 queue。因为如果只加入队列却不立刻标记那么在这个格子真正被popleft()之前有可能又被其他邻居发现一次导致重复进入队列。六、完整代码思路捋清楚以后我再尝试自己写classSolution:defnumIslands(self,grid:List[List[str]])-int:mlen(grid)nlen(grid[0])count0visitedset()directions[(-1,0),(1,0),(0,-1),(0,1)]foriinrange(m):forjinrange(n):ifgrid[i][j]1and(i,j)notinvisited:visited.add((i,j))count1queuedeque([(i,j)])whilequeue:row,colqueue.popleft()fordr,dcindirections:new_rowrowdr new_colcoldcif(0new_rowmand0new_colnandgrid[new_row][new_col]1and(new_row,new_col)notinvisited):visited.add((new_row,new_col))queue.append((new_row,new_col))returncount完整提交时还需要fromcollectionsimportdequefromtypingimportList七、写的时候踩到的一个小坑这里是字符串1我一开始写的是grid[i][j]1但这道题的类型是List[List[str]]也就是说grid里面存的是字符串0 1不是整数0 1所以应该写grid[i][j]1BFS 里面同样应该是grid[new_row][new_col]1这个和算法本身没什么关系但如果没有注意输入类型整体思路明明是对的代码却还是会判断失败。八、为什么这里没有把0也加入 visited一开始我还会想BFS 遇到0以后停止那这个0要不要也算 visited其实不需要。因为visited在这道题里主要是为了记录哪些陆地已经属于以前发现过的岛。而0本来就不能继续进入。判断中已经有grid[new_row][new_col]1如果邻居是0BFS 自然不会进入它。所以1 → 可能属于某座岛 → 需要记录 visited 0 → 海水 → 本来就不会进入 BFS → 直接跳过没有必要再额外保存所有的0。九、 复杂度假设m grid 的行数 n grid 的列数外层双循环会扫描整个网格m × n而 BFS 中每一个陆地最多只会被真正加入visited一次。所以整体时间复杂度是O(m × n)虽然代码里看起来有双循环 while queue但并不是O(m × n × m × n)因为 BFS 不会对每一个格子重新遍历整张地图。一个陆地被第一次 BFS 访问以后就会进入visited后面不会再次被处理。空间方面visited最坏可能保存整个网格的陆地坐标queue最坏也可能保存大量待处理格子。所以最坏空间复杂度为O(m × n)十、从 733 到 200又学了什么做完以后再回头看733 已经架构了这个流程给定一个起点 ↓ 检查上下左右 ↓ 找到符合要求的邻居 ↓ 标记 ↓ 加入 queue ↓ 把整块连通区域找出来而 200 增加就是外面这一层扫描整个 grid ↓ 寻找没有访问过的 1 ↓ 发现新的岛 ↓ count 1 ↓ 用 BFS 把整座岛标记掉 ↓ 继续扫描所以这道题最重要的理解应该是BFS 并不是用来判断“这一块是不是一座岛”而是当代码已经碰到一块新的陆地以后用来把和它连通的整座岛全部找出来。而真正判断这里是不是一座新的岛靠的是grid[i][j]1and(i,j)notinvisited因为如果它属于以前的岛 → 以前的 BFS 早就访问过它 现在它仍然没有 visited → 以前的岛都到不了这里 所以 → 发现一座新岛这也是从 733 到 200 最关键的一步。可以把整个过程最后压缩成双循环 → 找新岛 发现没访问过的 1 → count 1 BFS → 把整座岛 visited 回到双循环 → 找下一座岛