新闻详情

新闻详情

首页 / 资讯中心 / 详情

BFS算法解决FloodFill问题

发布时间:2026/11/16 16:15:03来源:尧图网络
BFS算法解决FloodFill问题
BFS算法解决FloodFill问题图像渲染岛屿数量岛屿的最大面积被围住的区域图像渲染题目解析就是将这里面指定一个元素将其上下左右和这个一样的值全部修改成另外一个值并且其上下左右也可以进行上下左右进行扩展也就是将这个一片区域都修改成color指定值BFS直接遍历所有下标并且看其上下左右下标不断进行修改不断进行扩展延申此时就可以使用队列放入 int[ ] 数组对应存放行、列下标每一次不断取出进行上下左右延申判断其是否和image[sr][sc]如果一样就继续放入队列中不断进行操作直到队列为空这里通过上下左右对应下标分别classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};publicint[][]floodFill(int[][]image,intsr,intsc,intcolor){intprevimage[sr][sc];if(prevcolor){//如果要修改和修改的一样此时就不需要修改returnimage;}intmimage.length;intnimage[0].length;//存放其下标Queueint[]queuenewLinkedList();queue.add(newint[]{sr,sc});while(!queue.isEmpty()){int[]temqueue.poll();intatem[0];//行intbtem[1];//列//将这个颜色修改image[a][b]color;//看这个位置前后左右位置for(inti0;i4;i){intxadx[i];intybdy[i];if(x0xmy0ynimage[x][y]prev){queue.add(newint[]{x,y});}}}returnimage;}}岛屿数量题目解析此时1表示岛屿并且1的上下左右如果有1的话就会进行延申展开最终求出有多少岛屿BFS遍历整个数组但是此时一个岛屿需要延申到不能延申为止这样才成为一个岛屿此时会出现问题我们会不断扩展后面遍历到这个位置又会让其岛屿数量1此时就重复统计了这里有两种解决方案方案一每次遍历过的位置将这里的 1 修改成 0方案二创建一个同等规模的数组如果统计过了就进行标记一下classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};boolean[][]visited;//标记已经遍历过的位置intm0;intn0;publicintnumIslands(char[][]grid){mgrid.length;ngrid[0].length;visitednewboolean[m][n];intret0;for(inti0;im;i){for(intj0;jn;j){//当时1并且没有遍历过结果if(grid[i][j]1visited[i][j]false){ret;dfs(grid,i,j);//将其旁边的visited都标记为遍历过}}}returnret;}publicvoiddfs(char[][]grid,inti,intj){Queueint[]queuenewLinkedList();queue.add(newint[]{i,j});visited[i][j]false;while(!queue.isEmpty()){int[]temqueue.poll();intatem[0];intbtem[1];for(intk0;k4;k){intxadx[k];intybdy[k];if(x0xmy0yngrid[x][y]1!visited[x][y]){queue.add(newint[]{x,y});visited[x][y]true;}}}}}岛屿的最大面积题目解析就是找出岛屿最大面积思想此时和上一题岛屿数量类似此时我们只需要在dfs方法中返回此时岛屿数量即可classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};boolean[][]visited;//标记已经遍历过的intm0;intn0;publicintmaxAreaOfIsland(int[][]grid){intret0;mgrid.length;ngrid[0].length;visitednewboolean[m][n];//此时遍历这个岛屿的时候统计一下它的面积返回for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1visited[i][j]false){//此时更新结果retMath.max(ret,dfs(grid,i,j));}}}returnret;}publicintdfs(int[][]grid,inti,intj){intcount0;//此时岛屿面积Queueint[]queuenewLinkedList();queue.add(newint[]{i,j});visited[i][j]true;count;while(!queue.isEmpty()){//队列为空就结束int[]temqueue.poll();intatem[0];intbtem[1];for(intk0;k4;k){intxadx[k];intybdy[k];//延申if(x0xmy0yngrid[x][y]1visited[x][y]false){queue.add(newint[]{x,y});visited[x][y]true;count;}}}returncount;}}被围住的区域题目解析就是将被X围住的O修改成X,未被围住的不做修改思想由于以前是一边遍历一边修但是这里会出现不需要修改的问题可能修改一半发现不需要修改此时这里还需要进行二次判断因此这里采用正难则反的思想1.先使用dfs遍历边界此时将边界及其扩展部分修改成 其他字符2.最后遍历一遍数组将剩下未被修改的O修改成X将这里被修改成其他字符的修改回以前的O字符classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};intm0;intn0;publicvoidsolve(char[][]board){mboard.length;nboard[0].length;//1.将边界的O以及相邻的O全部修改成 . 最后在修改回来//左右两列for(inti0;im;i){if(board[i][0]O){dfs(board,i,0);}if(board[i][n-1]O){dfs(board,i,n-1);}}//上下两行for(inti0;in;i){if(board[0][i]O){dfs(board,0,i);}if(board[m-1][i]O){dfs(board,m-1,i);}}//剩下的O修改成X将上面修改的还原for(inti0;im;i){for(intj0;jn;j){if(board[i][j]O){board[i][j]X;//修改回来}elseif(board[i][j].){board[i][j]O;}}}}publicvoiddfs(char[][]board,inti,intj){Queueint[]queuenewLinkedList();queue.add(newint[]{i,j});board[i][j].;//修改成.while(!queue.isEmpty()){int[]temqueue.poll();intatem[0];intbtem[1];for(intk0;k4;k){intxadx[k];intybdy[k];if(x0xmy0ynboard[x][y]O){queue.add(newint[]{x,y});board[x][y].;}}}}}
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/17 7:04:08

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/17 5:42:44

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/17 6:55:04

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/17 5:57:47

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉