1.前言来看下图floodfill解决的是一个大区域里有很多小区域找出性质相同的连通块(上下左右连)。做法无非是从左往右扫描过程中发现低谷的时候来一次深度或宽度优先遍历一个地方走不通回溯到上一个位置继续遍历。2.图像渲染733. 图像渲染 - 力扣LeetCodehttps://leetcode.cn/problems/flood-fill/description/看图深度优先遍历以这个位置为起点开始上下左右扫描。当扫描到和我像素值相同的区域后就递归进去但递归前别忘了把这块区域改为新的像素。所以从这个位置开始的时候先把它改为2然后上下左右遍历。因为深搜所以这有2种方向时先选1个方向走。假设这往上走走上去后这个位置的值改为2然后以它为起点上下左右搜索假设往左走走不了后回溯最终回溯回去。虽然可以往左走但往上走后左边已经修改过了此时不能走了递归结束。说个细节如果new是1这样第二个位置扩展时可能回去所以1的情况判断了直接返回。下面实现2.岛屿数量200. 岛屿数量 - 力扣LeetCodehttps://leetcode.cn/problems/number-of-islands/description/如图找连通块的数量就一行行的扫描当扫到第一个1的时候就把以这个1相连的区域都标记一下此时相当于找到了一块陆地。继续扫描碰到被标记过的1不做统计扫到没标记过的1相当于此时又找到了一个连通块用变量记录后再把与这个1连接的岛屿记录一下这样依次类推。如何做到标记呢弄一个vis[][]标记数组就行了。下面来实现3.岛屿的最大面积695. 岛屿的最大面积 - 力扣LeetCodehttps://leetcode.cn/problems/max-area-of-island/description/依次扫描扫描到陆地后就由这个陆地开始来一次深度优先遍历。可以弄一个count 只要进入深度优先遍历一次就让count深度优先遍历结束后count就统计的是这块岛屿的面积。可再用 ret统计所有count里的最大值。下面来实现4.被围绕的区域130. 被围绕的区域 - 力扣LeetCodehttps://leetcode.cn/problems/surrounded-regions/description/如图我们期望最终把绿框中的两个0变X就行。刚开始想到的策略是依旧扫描一下矩阵当碰到0时就开始沿着点来一次深度优先遍历。但有些区域是不能改的所以深度优先遍历碰到非法位置的时候就向上回溯但这样代码很难写。我们要用正难则反的思想先把和边界有关的区域处理一下剩下的自然是在内部的0。怎么处理边界呢扫描边界碰到0后来一次深度优先遍历都标记一下(这可把它们处理为点)接下来扫描时碰到点还原为 0碰到0修改为X。下面实现5.太平洋大西洋水流问题417. 太平洋大西洋水流问题 - 力扣LeetCodehttps://leetcode.cn/problems/pacific-atlantic-water-flow/description/这道题给了我们一个矩阵这个矩阵相当于一个陆地。这个陆地被两个洋包围其中左以及上代表太平洋右以及下代表大西洋。这个陆地上有很多数字其中数字代表高度其中某个格子有水的话水可以流向周围比它低或与它相等的格子。题目问的是在这所有小格子中能否存在一个位置这个位置的水既可流向太平洋也可流向大西洋有的话把坐标存下来最终返回。有一种解法是暴力枚举这里面所有的点遇到一个点判断一下能否去太平洋和大西洋。这样方式会考虑到重复路径一旦矩阵规模大就会超时。我们要用正难则反策略我们先看边界上的水它能去哪些位置。比如从1位置开始考虑接下来就看大于等于我的位置所以这么多点都可经过1流向太平洋。从1开始搜索第一行就判断完了下面考虑太平洋这一列从2开始扩展然后是5(因为其余位置标记过了)发现这些标记的都可流向太平洋。下面再判断哪些点能经过靠近大西洋的一行一列流向大西洋那些被重复标记的点既能流向太平洋也能流向大西洋下面实现6.扫雷游戏529. 扫雷游戏 - 力扣LeetCodehttps://leetcode.cn/problems/minesweeper/description/如图点击这个位置后我们要先判断点击位置当点击位置周围没有地雷的话相当于它就是一个空方格此时要递归的把周围方格都打开每次进入新格子递归时先判断周围有没有地雷没有就把周围打看同时改为B。若周围有地雷比如有一个就把当前位置改为1然后停止该层的递归返回上一层。这有个细节是把之前四向量数组改为八向量数组下面来实现7.机器人的运动范围LCR 130. 衣橱整理 - 力扣LeetCodehttps://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/如图其实就是从(0,0)位置开始来一次深度优先遍历把能够进入的格子统计一下就行。能够进入格子的特性是数位之和小于等于cnt。下面实现 FloodFill算法
1.前言来看下图floodfill解决的是一个大区域里有很多小区域找出性质相同的连通块(上下左右连)。做法无非是从左往右扫描过程中发现低谷的时候来一次深度或宽度优先遍历一个地方走不通回溯到上一个位置继续遍历。2.图像渲染733. 图像渲染 - 力扣LeetCodehttps://leetcode.cn/problems/flood-fill/description/看图深度优先遍历以这个位置为起点开始上下左右扫描。当扫描到和我像素值相同的区域后就递归进去但递归前别忘了把这块区域改为新的像素。所以从这个位置开始的时候先把它改为2然后上下左右遍历。因为深搜所以这有2种方向时先选1个方向走。假设这往上走走上去后这个位置的值改为2然后以它为起点上下左右搜索假设往左走走不了后回溯最终回溯回去。虽然可以往左走但往上走后左边已经修改过了此时不能走了递归结束。说个细节如果new是1这样第二个位置扩展时可能回去所以1的情况判断了直接返回。下面实现2.岛屿数量200. 岛屿数量 - 力扣LeetCodehttps://leetcode.cn/problems/number-of-islands/description/如图找连通块的数量就一行行的扫描当扫到第一个1的时候就把以这个1相连的区域都标记一下此时相当于找到了一块陆地。继续扫描碰到被标记过的1不做统计扫到没标记过的1相当于此时又找到了一个连通块用变量记录后再把与这个1连接的岛屿记录一下这样依次类推。如何做到标记呢弄一个vis[][]标记数组就行了。下面来实现3.岛屿的最大面积695. 岛屿的最大面积 - 力扣LeetCodehttps://leetcode.cn/problems/max-area-of-island/description/依次扫描扫描到陆地后就由这个陆地开始来一次深度优先遍历。可以弄一个count 只要进入深度优先遍历一次就让count深度优先遍历结束后count就统计的是这块岛屿的面积。可再用 ret统计所有count里的最大值。下面来实现4.被围绕的区域130. 被围绕的区域 - 力扣LeetCodehttps://leetcode.cn/problems/surrounded-regions/description/如图我们期望最终把绿框中的两个0变X就行。刚开始想到的策略是依旧扫描一下矩阵当碰到0时就开始沿着点来一次深度优先遍历。但有些区域是不能改的所以深度优先遍历碰到非法位置的时候就向上回溯但这样代码很难写。我们要用正难则反的思想先把和边界有关的区域处理一下剩下的自然是在内部的0。怎么处理边界呢扫描边界碰到0后来一次深度优先遍历都标记一下(这可把它们处理为点)接下来扫描时碰到点还原为 0碰到0修改为X。下面实现5.太平洋大西洋水流问题417. 太平洋大西洋水流问题 - 力扣LeetCodehttps://leetcode.cn/problems/pacific-atlantic-water-flow/description/这道题给了我们一个矩阵这个矩阵相当于一个陆地。这个陆地被两个洋包围其中左以及上代表太平洋右以及下代表大西洋。这个陆地上有很多数字其中数字代表高度其中某个格子有水的话水可以流向周围比它低或与它相等的格子。题目问的是在这所有小格子中能否存在一个位置这个位置的水既可流向太平洋也可流向大西洋有的话把坐标存下来最终返回。有一种解法是暴力枚举这里面所有的点遇到一个点判断一下能否去太平洋和大西洋。这样方式会考虑到重复路径一旦矩阵规模大就会超时。我们要用正难则反策略我们先看边界上的水它能去哪些位置。比如从1位置开始考虑接下来就看大于等于我的位置所以这么多点都可经过1流向太平洋。从1开始搜索第一行就判断完了下面考虑太平洋这一列从2开始扩展然后是5(因为其余位置标记过了)发现这些标记的都可流向太平洋。下面再判断哪些点能经过靠近大西洋的一行一列流向大西洋那些被重复标记的点既能流向太平洋也能流向大西洋下面实现6.扫雷游戏529. 扫雷游戏 - 力扣LeetCodehttps://leetcode.cn/problems/minesweeper/description/如图点击这个位置后我们要先判断点击位置当点击位置周围没有地雷的话相当于它就是一个空方格此时要递归的把周围方格都打开每次进入新格子递归时先判断周围有没有地雷没有就把周围打看同时改为B。若周围有地雷比如有一个就把当前位置改为1然后停止该层的递归返回上一层。这有个细节是把之前四向量数组改为八向量数组下面来实现7.机器人的运动范围LCR 130. 衣橱整理 - 力扣LeetCodehttps://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/如图其实就是从(0,0)位置开始来一次深度优先遍历把能够进入的格子统计一下就行。能够进入格子的特性是数位之和小于等于cnt。下面实现