【BFS/DFS 解决 FloodFill 算法】图像渲染-北京尧图网络

文章目录题目解析方向向量BFS广度优先遍历算法原理细节问题边界情况代码实现DFS深度优先遍历算法原理全局变量dfs 函数函数头函数体细节问题边界情况代码实现题目链接733. 图像渲染题目解析首先介绍一下什么是FloodFill算法FloodFill算法也称为洪水填充算法指的是在区域中找到性质相同的联通块注意这里的联通块指的是上下左右相邻斜线不能算做相邻。该算法可以使用深度优先搜索和广度优先搜索来解决。我们回到题目题目给我们一个由整数组成的二维矩阵image其中的数字表示像素值。题目同时给出sr、sc和color分别表示起始位置 image[sr][sc] 和目标色块。我们需要从起始位置开始找到所有与初始位置色块相邻的其他色块色块相同并将色块修改成color。例一image [ [ 1, 1, 1 ], [ 1, 1, 0 ], [ 1, 0, 1 ] ]sr 1, sc 1, color 2image 表示为如下网格111110101所有红色的区域就是性质相同的联通块。修改后的 image 网格222220201例二image [ [ 0, 0, 0 ], [ 0, 0, 0 ] ]sr 0, sc 0, color 0000000000这个例子中其实位置的像素值与 color 一致无需修改直接返回即可。方向向量在继续之前有必要知道我们在解决矩阵搜索类问题时访问某位置上下左右四个方向的操作。坐标〖i, j〗的上下左右四个坐标是在i和j加上了 0、1、-1 上下坐标〖i (-1), j 0〗和〖i 1, j 0〗左右坐标〖i 0, j (-1)〗和〖i 0, j 1〗。因此需要定义两个向量坐标dx {0, 0, -1, 1}dy {-1, 1, 0, 0}。在需要访问时通过〖row, col〗坐标和四次循环依次访问即可。BFS广度优先遍历算法原理我们使用一个队列存储需要被修改像素值的方格的坐标以数组的形式表示坐标然后当队列不为空时就一直弹出队首元素将该位置的像素值修改修改完成后循环四次访问该位置的四周通过队首元素得到的坐标计算该位置的上下左右四个方向的坐标并检查合法性将合法的位置存入队列中准备修改当层序遍历完成后返回修改后的图像即可细节问题边界情况从示例 2 可以知道可能存在原像素值与color相同的情况。这种情况下我们不需要修改任何方格直接返回原图像即可。代码实现classSolution{// 辅助访问某位置上下左右四个方向的方向向量int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};publicint[][]floodFill(int[][]image,intsr,intsc,intcolor){intoriginColorimage[sr][sc];// 记录原色像素值if(originColorcolor){// 处理边界情况returnimage;}intmimage.length,nimage[0].length;// 记录图像的尺寸Queueint[]queuenewArrayDeque();// 用队列记录需要修改的色块的坐标queue.offer(newint[]{sr,sc});// 从位置[sr,sc]开始宽搜// 层序遍历while(!queue.isEmpty()){int[]topqueue.poll();// 获取队首introwtop[0],coltop[1];// 记录坐标image[row][col]color;// 修改色块// 从位置[row,col]的上下左右四个方向宽搜for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0ynimage[x][y]originColor){// 符合需要被修改的条件入队queue.offer(newint[]{x,y});}}}// 返回修改后的结果returnimage;}}DFS深度优先遍历算法原理直接从起始位置开始深搜对每一个指定位置的上下左右四个方向按照特定的条件搜索然后修改其像素值为 color直到没有符合条件的方格为止当所有方格被搜索过之后递归结束返回修改后的图像即可全局变量为了递归方便我们将题目给出的image改为全局变量同时m和n记录矩阵的大小。然后是originColor用于记录起始位置的原像素值题目给出的color然后是两个向量数组dx和dy。int[][]image;intoriginColor,color,m,n;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};dfs 函数函数头dfs 函数的任务是帮助我们搜索指定位置的上下左右四个方位并且根据指定条件修改方格的像素值。我们这里的参数是某个位置的坐标row和col函数的返回值为 void。dfs(introw,intcol);函数体我们循环四次然后判断坐标是否合法如果合法就看看该位置的像素值是否与起始位置的原像素值相同该位置的像素值是否与 color 不同如果同时满足 “与起始位置的原像素值相同” 和 “与 color 不同”就将该位置的像素值修改成 color然后基于这个位置继续深搜。细节问题边界情况当原像素值与color相同不需要修改直接返回原图像即可。代码实现classSolution{int[][]image;intoriginColor,color,m,n;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};publicint[][]floodFill(int[][]givenImage,intsr,intsc,intgivenColor){imagegivenImage;colorgivenColor;mimage.length;nimage[0].length;// 从[sr,sc]位置开始递归递归前先记录原像素值originColorimage[sr][sc];// 判断当前的像素值是否与color相同不同就修改if(originColor!color){image[sr][sc]color;}dfs(sr,sc);returnimage;}privatevoiddfs(introw,intcol){// 从[row,col]位置开始向四个方向搜索for(intk0;k4;k){intxrowdx[k],ycoldy[k];// 判断下标是否合法if(x0xmy0yn){// 判断当前位置的像素值是否与起始位置的像素值相同并且是否与color不同if(image[x][y]originColorimage[x][y]!color){// 修改像素值image[x][y]color;dfs(x,y);}}}}}文章到这里就告一段落了若有错误请尽管指出完

【BFS/DFS 解决 FloodFill 算法】图像渲染

相关推荐

精准广告投放系统

基于结构化索引提升智能体F1分数：CTIFoundry理念与LangChain实战

Windows 11 玩老游戏闪退黑屏？3 步用 DDrawCompat 修好 DirectDraw 兼容的完整指南

更多资讯

电工证复审补救方法：怕考不过白交培训费？上岗必备技巧全在这儿

电工证挂靠有什么手续上岗必须要这个证吗

云南省电工证查询网模拟考试题库：值不值得考？工地太忙根本没时间复习考试

电工作业流程图有效期多久？官方报名入口怎么找

电工作业流程图郑州报考避坑指南怎么找靠谱的报名渠道

怀仁可以考电工证吗？考前押题攻略教你一次过！

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？