论坛做视频网站,建设工程机械职业技能鉴定,企业黄页到哪里买,图片 网站源码目录
什么是floodfill算法
题目一——733. 图像渲染 - 力扣#xff08;LeetCode#xff09;
题目二——200. 岛屿数量 - 力扣#xff08;LeetCode#xff09;
题目三——695. 岛屿的最大面积 - 力扣#xff08;LeetCode#xff09;
题目四—— 130. 被围绕的区域 …目录
什么是floodfill算法
题目一——733. 图像渲染 - 力扣LeetCode
题目二——200. 岛屿数量 - 力扣LeetCode
题目三——695. 岛屿的最大面积 - 力扣LeetCode
题目四—— 130. 被围绕的区域 - 力扣LeetCode
题目五——417. 太平洋大西洋水流问题 - 力扣LeetCode
题目六——529. 扫雷游戏 - 力扣LeetCode
题目七——LCR 130. 衣橱整理 - 力扣LeetCode 什么是floodfill算法
啥是 FloodFill 算法呢最直接的一个应用就是「颜色填充」就是 Windows 绘画本中那个小油漆桶的标志可以把一块被圈起来的区域全部染色。 这种算法思想还在许多其他地方有应用。比如说扫雷游戏有时候你点一个方格会一下子展开一片区域这个展开过程就是 FloodFill 算法实现的。 类似的像消消乐这类游戏相同方块积累到一定数量就全部消除也是 FloodFill 算法的功劳。 通过以上的几个例子你应该对 FloodFill 算法有个概念了现在我们要抽象问题提取共同点。
实现这个FloodFill算法其实有两种实现方式
DFSBFS
我们这篇文章只讲解DFS里面的
题目一——733. 图像渲染 - 力扣LeetCode 这个题目很容易懂吧其实我们只需要从题目给的那个起始位置开始调用dfs。每遍历一个我们就将它的颜色改成
class Solution {
public:// 定义四个方向的移动向量用于上下左右四个方向的遍历int dx[4]{0,0,-1,1}; // x方向上的移动-1左1右0不变int dy[4]{1,-1,0,0}; // y方向上的移动1上-1下0不变// 深度优先搜索函数用于将指定起始点的相连区域的颜色更改为目标颜色void dfs(vectorvectorint image, int i, int j, int origincolor, int tar_color){// 将当前点的颜色更改为目标颜色image[i][j] tar_color;// 遍历四个方向for(int k0; k4; k){int x i dx[k], y j dy[k]; // 计算相邻点的坐标// 检查相邻点是否在图像范围内且颜色与起始颜色相同if(x 0 x image.size() y 0 y image[0].size() image[x][y] origincolor){// 如果满足条件则递归地对相邻点进行深度优先搜索dfs(image, x, y, origincolor, tar_color);}}}// 图像渲染洪水填充的主函数vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {// 如果起始点的颜色已经等于目标颜色则无需更改直接返回原图像if(image[sr][sc] color) return image;// 调用深度优先搜索函数从起始点开始将相连区域的颜色更改为目标颜色dfs(image, sr, sc, image[sr][sc], color);// 返回渲染后的图像return image;}
}; 题目二——200. 岛屿数量 - 力扣LeetCode 其实我们之前做了那么多回溯的题目了我相信大家都会做这一道。
我们很快就能写出代码但是我们要考虑一点我们怎么判断我们走过了哪些点啊
有两种方法
我们可以修改我们遍历过的点——即将我们遍历过的点设置为2我们也可以使用一个和原数组等大的bool数组来记录我们走过的点 修改我们遍历过的点 class Solution {
public:// 定义四个方向的移动上、下、左、右// dx数组表示在x方向上的移动dy数组表示在y方向上的移动int dx[4]{0,0,-1,1}; // x方向上的移动-1左1右0上/下时不变int dy[4]{1,-1,0,0}; // y方向上的移动1上-1下0左/右时不变// 深度优先搜索函数用于遍历并标记所有相连的1为2void dfs(vectorvectorchar grid, int i, int j) {// 将当前位置标记为已访问过2grid[i][j] 2;// 遍历四个方向for (int k 0; k 4; k) {// 计算新位置的坐标int x i dx[k], y j dy[k];// 检查新位置是否在网格内且为1未访问过的岛屿部分if (x 0 x grid.size() y 0 y grid[0].size() grid[x][y] 1) {// 如果是则递归访问该位置dfs(grid, x, y);}}}// 计算岛屿数量的函数int numIslands(vectorvectorchar grid) {int ret 0; // 记录岛屿数量// 遍历整个网格for (int n 0; n grid.size(); n) {for (int i 0; i grid[0].size(); i) {// 如果当前位置是1岛屿的起始点if (grid[n][i] 1) {// 调用dfs函数遍历并标记这个岛屿的所有部分dfs(grid, n, i);// 岛屿数量加一ret;}}}// 返回岛屿的总数量return ret;}
}; 使用bool数组版本 class Solution {
public:// 用于记录网格中每个位置是否已被访问过的二维数组bool check[301][301]{false}; // 假设网格的大小不会超过300x300// 定义四个方向的移动上、下、左、右// dx数组表示在x方向上的移动dy数组表示在y方向上的移动int dx[4] {0, 0, -1, 1}; // x方向上的移动-1左1右0上/下时不变但在这里主要用于配合dy进行方向移动int dy[4] {1, -1, 0, 0}; // y方向上的移动1上-1下0左/右时不变但在这里主要用于配合dx进行方向移动// 深度优先搜索函数用于遍历并标记所有相连的1为已访问虽然实际上并未改变grid中的值但使用了check数组来记录void dfs(vectorvectorchar grid, int i, int j) {// 将当前位置标记为已访问过check[i][j] true;// 遍历四个方向for (int k 0; k 4; k) {// 计算新位置的坐标int x i dx[k], y j dy[k];// 检查新位置是否在网格内、是否为1且未被访问过if (x 0 x grid.size() y 0 y grid[0].size() grid[x][y] 1 check[x][y] false) {// 如果是则递归访问该位置dfs(grid, x, y);}}}// 计算岛屿数量的函数int numIslands(vectorvectorchar grid) {int ret 0; // 记录岛屿数量// 遍历整个网格for (int n 0; n grid.size(); n) {for (int i 0; i grid[0].size(); i) {// 如果当前位置是1且未被访问过即是一个新岛屿的起点if (grid[n][i] 1 check[n][i] false) {// 调用dfs函数遍历并标记这个岛屿的所有部分dfs(grid, n, i);// 岛屿数量加一ret;}}}// 返回岛屿的总数量return ret;}
}; 题目三——695. 岛屿的最大面积 - 力扣LeetCode 和上题简直一模一样。我们还是考虑一个东西
我们很快就能写出代码但是我们要考虑一点我们怎么判断我们走过了哪些点啊
有两种方法
我们可以修改我们遍历过的点——即将我们遍历过的点设置为2我们也可以使用一个和原数组等大的bool数组来记录我们走过的点 修改原数组版本 class Solution {
public:// 定义四个方向的移动上、下、左、右// dx数组表示在x方向上的移动dy数组表示在y方向上的移动int dx[4] {0, 0, -1, 1}; // x方向上的移动-1左1右0上/下时不变但在这里主要用于配合dy进行方向移动int dy[4] {1, -1, 0, 0}; // y方向上的移动1上-1下0左/右时不变但在这里主要用于配合dx进行方向移动int path;void dfs(vectorvectorintgrid,int i,int j){grid[i][j]2;path;for(int k0;k4;k){int x i dx[k], y j dy[k];if (x 0 x grid.size() y 0 y grid[0].size() grid[x][y] 1) {dfs(grid,x,y); }}}int maxAreaOfIsland(vectorvectorint grid) {int ret0;for(int n0;ngrid.size();n){for(int i0;igrid[0].size();i){if(grid[n][i]1){path0;dfs(grid,n,i);retmax(path,ret);}}}return ret;}
}; 使用bool数组版本 class Solution {
public:// 定义四个方向的移动上、下、左、右// dx数组表示在x方向上的移动dy数组表示在y方向上的移动int dx[4] {0, 0, -1, 1}; // x方向上的移动-1左1右0上/下时不变但在这里主要用于配合dy进行方向移动int dy[4] {1, -1, 0, 0}; // y方向上的移动1上-1下0左/右时不变但在这里主要用于配合dx进行方向移动int path;bool check[51][51]{false};void dfs(vectorvectorintgrid,int i,int j){check[i][j]true;path;for(int k0;k4;k){int x i dx[k], y j dy[k];if (x 0 x grid.size() y 0 y grid[0].size() grid[x][y] 1check[x][y]false) {dfs(grid,x,y); }}}int maxAreaOfIsland(vectorvectorint grid) {int ret0;for(int n0;ngrid.size();n){for(int i0;igrid[0].size();i){if(grid[n][i]1check[n][i]false){check[n][i]true;path0;dfs(grid,n,i);retmax(path,ret);}}}return ret;}
}; 题目四—— 130. 被围绕的区域 - 力扣LeetCode 这道题相比于之前的floodfill算法题还是有一点难度的。
如果我们直接做是特别麻烦的所以我们需要转换一下思维——正难则反
我们不去直接修改里面的O我们先修改外围的‘O剩下的O就是我们要修改的
我们先处理边界的o遇到一个o就设置成.然后调用dfs寻找和它相连的o现在数组里面就只剩下x,.,o了 最后我们将.还原成x把o修改成x
我们就很快就能写出下面这个代码
class Solution {
public:// 定义四个方向上的行列偏移量用于DFS遍历int dx[4] {1, -1, 0, 0}; // 右、左、下、上int dy[4] {0, 0, 1, -1};// 深度优先搜索函数用于将与边界上的O相连的所有O标记为.void dfs(vectorvectorchar board, int i, int j) {board[i][j] .; // 将当前O标记为.表示已访问for (int k 0; k 4; k) { // 遍历四个方向int x i dx[k], y j dy[k]; // 计算新坐标// 检查新坐标是否越界且新位置的字符是否为Oif (x 0 x board.size() y 0 y board[0].size() board[x][y] O) {dfs(board, x, y); // 递归调用继续DFS}}}// 主函数用于执行整个棋盘的处理void solve(vectorvectorchar board) {int m board.size(), n board[0].size(); // 获取棋盘的行数和列数// 第一步把边界的O相连的联通块全部修改成.// 遍历棋盘的四个边界使用DFS将与边界上的O相连的所有O标记为.for (int j 0; j n; j) { // 遍历第一行和最后一行if (board[0][j] O) dfs(board, 0, j); // 第一行if (board[m - 1][j] O) dfs(board, m - 1, j); // 最后一行}for (int i 0; i m; i) { // 遍历第一列和最后一列if (board[i][0] O) dfs(board, i, 0); // 第一列if (board[i][n - 1] O) dfs(board, i, n - 1); // 最后一列}// 第二步还原// 将标记为.的字符还原为O表示这些O与边界相连将未标记的O转换为X表示这些O是孤立的for (int i 0; i m; i)for (int j 0; j n; j) {if (board[i][j] .) board[i][j] O; // 还原与边界相连的Oelse if (board[i][j] O) board[i][j] X; // 将孤立的O转换为X}}
}; 题目五——417. 太平洋大西洋水流问题 - 力扣LeetCode 看起来好恶心啊题目都没有看懂啊。
正难则反。
如果直接去判断某⼀个位置是否既能到⼤西洋也能到太平洋会重复遍历很多路径。
我们反着来从⼤西洋沿岸开始反向 dfs 这样就能找出那些点可以流向⼤西洋同理从太平洋沿 岸也反向 dfs 这样就能找出那些点可以流向太平洋。那么被标记两次的点就是我们要找的结 果。 class Solution {int m, n; // 用于存储矩阵的行数和列数int dx[4] {0, 0, 1, -1}; // 定义四个方向的x偏移量用于上下左右移动int dy[4] {1, -1, 0, 0}; // 定义四个方向的y偏移量用于上下左右移动public:// 主函数用于找到可以从太平洋和大西洋到达的陆地单元格vectorvectorint pacificAtlantic(vectorvectorint h) {m h.size(), n h[0].size(); // 初始化行数和列数vectorvectorbool pac(m, vectorbool(n, false)); // 标记可以从太平洋到达的单元格vectorvectorbool atl(m, vectorbool(n, false)); // 标记可以从大西洋到达的单元格// 1. 先处理太平洋方向从边界开始深度优先搜索for (int j 0; j n; j) dfs(h, 0, j, pac); // 从第一行的每个单元格开始搜索for (int i 0; i m; i) dfs(h, i, 0, pac); // 从第一列的每个单元格开始搜索// 2. 处理大西洋方向从边界开始深度优先搜索for (int i 0; i m; i) dfs(h, i, n - 1, atl); // 从最后一行的每个单元格开始搜索for (int j 0; j n; j) dfs(h, m - 1, j, atl); // 从最后一列的每个单元格开始搜索vectorvectorint ret; // 存储结果即可以同时从太平洋和大西洋到达的单元格坐标// 遍历每个单元格检查是否同时被pac和atl标记为可达for (int i 0; i m; i)for (int j 0; j n; j)if (pac[i][j] atl[i][j])ret.push_back({i, j}); // 如果可以同时从两边到达则加入结果集return ret; // 返回结果}// 深度优先搜索函数用于标记可以从给定起点到达的所有单元格void dfs(vectorvectorint h, int i, int j, vectorvectorbool check) {check[i][j] true; // 标记当前单元格为可达for (int k 0; k 4; k) { // 遍历四个方向int x i dx[k], y j dy[k]; // 计算新坐标// 检查新坐标是否在矩阵范围内是否未被访问过且高度不小于当前单元格if (x 0 x m y 0 y n check[x][y] false h[x][y] h[i][j]) {dfs(h, x, y, check); // 递归调用继续搜索}}}
}; 题目六——529. 扫雷游戏 - 力扣LeetCode 这个题目就是吓你但是其实非常简单的
class Solution
{int dx[8] {0, 0, 1, -1, 1, 1, -1, -1}; // 八个方向的x偏移量用于八个方向的移动上下左右及四个对角线方向int dy[8] {1, -1, 0, 0, 1, -1, -1, 1}; // 八个方向的y偏移量用于八个方向的移动上下左右及四个对角线方向int m, n; // 矩阵的行数和列数public:// 更新地雷板的主函数vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {m board.size(); // 获取行数n board[0].size(); // 获取列数int x click[0], y click[1]; // 获取点击位置的坐标// 如果直接点到地雷if(board[x][y] M) {board[x][y] X; // 将地雷标记为X表示已点击return board; // 返回更新后的板}// 从点击位置开始进行深度优先搜索dfs(board, x, y);return board; // 返回更新后的板}// 深度优先搜索函数void dfs(vectorvectorchar board, int i, int j){// 统计一下周围的地雷个数int count 0;for(int k 0; k 8; k) // 遍历八个方向{int x i dx[k], y j dy[k]; // 计算新坐标// 如果新坐标在矩阵范围内且对应位置是地雷if(x 0 x m y 0 y n board[x][y] M){count; // 地雷计数加一}}// 如果周围有地雷if(count 0) {board[i][j] count 0; // 将当前位置标记为周围地雷的数量字符形式return; // 结束当前搜索}else // 如果周围没有地雷{board[i][j] B; // 将当前位置标记为B表示是安全的空地// 继续搜索周围未探索过的空地标记为E的位置for(int k 0; k 8; k){int x i dx[k], y j dy[k];// 如果新坐标在矩阵范围内且对应位置是未探索过的空地Eif(x 0 x m y 0 y n board[x][y] E){dfs(board, x, y); // 递归调用继续搜索}}}}
}; 题目七——LCR 130. 衣橱整理 - 力扣LeetCode class Solution {
public:int m, n, k; // 矩阵的行数m、列数n和给定的和限制kbool vis[101][101]; // 访问标记数组用于记录哪些位置已经被访问过int ret; // 结果变量用于记录满足条件的路径数量或深度优先搜索的访问次数等具体含义取决于dfs函数的实现int dx[4] {0, 0, -1, 1}; // 四个方向的x偏移量用于上下左右移动int dy[4] {1, -1, 0, 0}; // 四个方向的y偏移量用于上下左右移动int wardrobeFinishing(int _m, int _n, int _k) {m _m, n _n, k _k; // 初始化矩阵大小和和限制dfs(0, 0); // 从(0, 0)位置开始进行深度优先搜索return ret; // 返回结果}// 深度优先搜索函数void dfs(int i, int j) {ret; // 访问次数加一vis[i][j] true; // 标记当前位置为已访问// 遍历四个方向for (int k 0; k 4; k) {int x i dx[k], y j dy[k]; // 计算新坐标// 检查新坐标是否在矩阵范围内、是否未被访问过以及是否满足某种条件通过check函数if (x 0 x m y 0 y n !vis[x][y] check(x, y))dfs(x, y); // 如果满足条件则递归调用dfs函数继续搜索}}// 坐标(i, j)的数字和是否小于等于kbool check(int i, int j) {int tmp 0;// 计算坐标i的数字和while (i) {tmp i % 10;i / 10;}// 计算坐标j的数字和while (j) {tmp j % 10;j / 10;}// 返回是否满足条件数字和是否小于等于kreturn tmp k;}
};
