【递归，搜索与回溯算法 & floodfill 算法】深入理解 floodfill 算法：floodfill 算法小专题
图像渲染
题目解析
算法原理
解法：暴搜
模拟过程
递归过程：
回溯过程：
处理细节问题
但是如果在上述矩阵的情况下，给我们的 color 不是 2 ，而是 1，也就是原始像素值和要修改像素值相同的情况，此时很有可能在递归的时候走重复路径：
我们不处理好这种特殊的情况，就很容易会写出 bug；所以在编写代码的时候，我们先判断一下，if (image[sr][sc]==color)，直接返回即可，因为无需修改；
编写代码
报错原因：没有修改 image[ sr ][ sc ] 为 color
优化：本题并不需要 vis 数组来标记走过的格子，因为走过的格子都会修改，修改后会被剪枝条件筛查掉，并且这道题也没有递归出口，也不需要恢复现场；
岛屿数量
题目解析
算法原理
解法：暴搜
处理细节问题
为了避免走重复路径，我们定义一个 vis ，用来标记已经走过的小方格 ：
编写代码
报错原因：
剪枝条件 grid[ x ][ y ] == ' 1 ' ，而不是 grid[ x ][ y ] == 1；
ret++ 设置的位置不对，是统计完一块岛屿的时候，ret 才+1，而上面这样设置，是在一块陆地（一个小格子）上下左右都查找完之后 +1，而不是找到一个完整的岛屿，ret 才+1；
在下图 ret++ 设置的位置，表示以 grid[ i ][ j ] 这块陆地开始递归，向外查找别的陆地，直到找完整块联通的陆地，递归才会结束；
递归结束，表明已经找到了以 grid[ i ][ j ] 这块陆地为起点所形成的一个完整的岛屿，ret++；
fillflood 部分
思考 ：做了那么多题目，为什么有的题目需要恢复现场，有的题目不需要恢复现场呢？
恢复现场是因为决策树衍生出的多条分支，为了保证每条分支的结果，不被同层的其他已经递归过的分支影响，回溯时，就要把其他分支修改的 path 还原；
而这道题不用恢复现场，原因是因为大多数 fullfill 算法类型的题，是要找出一块矩阵所有的联通区，这些联通区需要被记录，因为这些联通区都会参与最终结果，且各个联通区不会出现重叠，所以在回溯时不需要也不能把记录过的联通区还原；
岛屿的最大面积
题目解析
算法原理
解法：暴搜
编写代码
报错原因：count 设置为 dfs 的一个参数，无法记录整个岛屿的面积，会出现只记录一部分，回溯时把记录部分恢复的情况；
被围绕的区域
题目解析
难点：如果联通的 O 区域中，只要有一块能在矩阵的边上，那么这一整块联通区 O 都不能被 X 包围，而这道题的难点就是处理这种情况；
算法原理
解法一：直接使用 floodfill 算法进行深度优先遍历
我们对一个联通区进行深度优先遍历，直到修改完联通区所有的 O ，但是如果遇到一块非法 O，我们就向上回溯，并且把修改成 X 的 O 全部恢复；
这个思路是可以的，但是代码会非常难写，因为被包围的联通区，和未被包围的联通区深度优先遍历的处理方法是不同的，按照这个思路，我们就需要写两份 dfs ；
并且还有一个更致命的问题，就是我们在进行深度优先遍历时，是先搜索，才能对一块小方块的合法与否进行判断，那么在判断之前，我们并不知道应该调用哪一份 dfs ；
解法二：正难则反
如果直接上手写代码比较难的话，我们可以采用正难则反的方法；
处理与边界相连的区域不好上手；那么我们就可以先处理矩阵的最外围，当最外围出现 O，就把O所在的联通区标记一下，此时剩下的 O ，就是我们应该处理的；
所以，我们可以在真正处理矩阵联通区之前，先扫描矩阵的四条边，如果四条边上扫描到 O， 我们就对这个 O 进行深度优先遍历，标记遍历到的联通区，剩下的联通区就是我们要处理的；
处理细节问题
这道题的标记方法，修改原始矩阵会比设置 vis 数组更好，因为这道题本来就是要修改原始矩阵:
编写代码
大体框架
fillflood 部分
总结
本题，我们又学会了正难则反的思想，以及如何遍历矩阵的四条边；
太平洋大西洋水流问题
题目解析
在看这道题之前，我们先来看看题目讨论：
这道题上面的题目的文字我们可以不看，煮啵会用示例一，来讲清楚这道题要我们做什么；
算法原理
解法一：枚举所有点并且直接判断
我们可以暴力枚举所有的点，如果一个点可以流向大西洋和太平洋，我们就把这个点的坐标存到最终的 ret 中 ；
如果直接判断，代码虽然不难写，但是会判断很多重复的路径：
比如图中这个 4，如果想去太平洋，可以通过暴搜，找到所有流向中，其中能流向太平洋的一条路径：
然后我们再来枚举高度为 5 的小格子，就有可能会判断到重复的路径：
枚举小方格使用直接判断的方法，是会判断多次重复路径的，如果这个矩阵的范围非常大，那么无效的时间开销也会变得非常大 ；
解法二：正难则反
我们最终要找的是某个点能不能流向太平洋，那我们就反过来看，我们可以假设太平洋的水逆着流，会流向哪些位置（水从海拔低的格子逆着流向海拔高或者等海拔的格子）
为了降低时间复杂度，遍历过的格子，就不用重新遍历：
而能流向大西洋的格子同理，让大西洋的水逆向流：
此时，重复的格子就是我们最终的返回值 ，这些重复格子既可以流向太平洋，也可以流向大西洋：
处理细节问题
编写代码
大框架
fillflood 部分
par ，atl 作为 dfs 的参数，把 par ，atl 设置成全局变量也可以，设置成局部变量也可以，都能起到记录的结果不会被自动恢复作用；
扫雷游戏
题目解析
算法原理
算法原理就是扫雷游戏的规则，我们可以自己去玩两把感受一下；
解法：模拟 + fillflood 深搜
我们以示例一来讲解扫雷游戏的步骤：
对于扫雷游戏：
处理细节问题
本题是八联通，需要扩展向量数组：
编写代码
准备工作
核心代码
机器人的运动范围
题目解析
原题
地上有一个m行n列的方格，从坐标[0,0]到坐标[m-1,n-1]。机器人从坐标[0,0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格[35,37]，因为3+5+3+7=18。但它不能进入方格[35,38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
算法原理
解法：深度优先遍历
通过一次深度优先遍历，找到满足： digit(i) + digit(j) <= cnt 性质的格子即可，本题的算法原理很简单，考验的是我们的代码能力；
编写代码
报错原因：不定义标记数组，ret 会统计重复走过的格子和递归回溯经过的格子的总数：
准备工作
核心代码
