BFS解决FloodFill算法:(Leetcode:733. 图像渲染)

题目链接:733. 图像渲染 - 力扣(LeetCode) 

使用广度优先遍历算法解决该问题:

从初始位置开始搜索,初始位置符合条件就入栈,并修改初始位置值。初始位置出栈。

再从初始位置开始广度优先搜索(上下左右)其他符合条件的位置入栈,并修改它们的值(搜索到即修改,防止同一位置被多次入栈)。每次出栈一个位置,并再次从该位置广度优先搜索,循环直至栈空。

typedef pair<int,int> PII;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        //处理边界条件(初始位置即为color则不需要修改)
        if(image[sr][sc]==color)
            return image;
        
        //广度优先搜索
        int prev=image[sr][sc];//记录初始位置的值
        queue<PII> q;
        q.push({sr,sc});//将初始位置入栈
        image[sr][sc]=color;//修改值
        int m=image.size();//行数,纵坐标边界值
        int n=image[0].size();//列数,横坐标边界值
        while(q.size())
        {
            int a=q.front().first;
            int b=q.front().second;
            q.pop();//出栈
            //广度优先搜索
            for(int i=0;i<4;++i)
            {
                int x=a+dx[i];
                int y=b+dy[i];
                if(x>=0&&y>=0&&x<m&&y<n&&image[x][y]==prev)
                {
                    q.push({x,y});
                    image[x][y]=color;//修改值
                }
            }
        }
        return image;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/569984.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

IDM下载器安装cmd注册

一、下载注册 安装包去IDM官网下载最新的试用版即可 或者直达百度网盘下载&#xff08;担心被河蟹&#xff0c;放在txt中了&#xff09;包含IDM下载器安装包和注册软件 IDM下载器安装包和注册软件下载地址链接 https://download.csdn.net/download/qq_31237581/89215452 如果…

sscanf和scanf区别

sscandf 从字符串中提取数据 scanf 标准输入流读取数据 int num; sscanf("42", "%d", &num);float f; sscanf("3.14", "%f", &f);char str[20]; sscanf("Hello, World!", "%s", str);int a, b; sscanf(…

vue3 引入@tsparticles/vue3和@tsparticles/slim 实现粒子特效

1.安装&#xff1a; yarn add tsparticles/vue3 tsparticles/slim2.main.ts 引入 import Particles from "tsparticles/vue3"; import { loadSlim } from "tsparticles/slim";app.use(Particles as any, {init: async (engine: any) > {await loadSli…

POJO,Entity,model,domain,view,DTO,VO,Param这些分别都是什么含义?怎样理解?

目录 1. 前言 2. POJO的含义 3. entity(实体) 4. model(模型) 5. domain(域) 6. view(视图) 7. DTO(数据传输对象) 8. VO(真正视图层) 9. Param(参数) 10. 总结 1. 前言 在日常开发的过程中&#xff0c;如果我们接手一个新的项目之后&#xff0c;通常会有各种各样的…

edu邮箱官方购买渠道手把手选购指南记录

教育优惠&#xff0c;是一项针对于在校大学生和教职员工推出的特殊优惠活动。一些公司会将旗下产品或服务以一定的折扣&#xff0c;甚至免费提供给高校师生。想想自己上大学的时候啥都不知道,毕业后才发现浪费了这么多优秀的资源.如果你还是一名在校大学生&#xff0c;那么就不…

40. 【Android教程】AsyncTask:异步任务

在前面的章节有提到过&#xff0c;Android 系统默认会在主线程&#xff08;UI 线程&#xff09;执行任务&#xff0c;但是如果有耗时程序就会阻塞 UI 线程&#xff0c;导致页面卡顿。这时候我们通常会将耗时任务放在独立的线程&#xff0c;然后通过 Handler 等线程间通信机制完…

扁平与圆形Cat6网线:区别与选择指南

&#x1f335;在构建家庭或办公室网络时&#xff0c;选择合适的网线类型至关重要。Cat6网线因其高速传输性能而广受欢迎&#xff0c;但在购买时&#xff0c;您可能会发现市场上有两种不同形状的Cat6网线&#xff1a;扁平和圆形。本文将探讨这两种网线的区别&#xff0c;并提供选…

用html写一个旋转菜单

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>旋转菜单</title><link relstylesheet href"https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.css"&…

百兆集成网络链接器911105A

百兆集成网络链接器&#xff08;有时也称为百兆网卡&#xff09;是一种硬件设备&#xff0c;主要用于计算机与计算机网络之间的高速数据传输。它的主要功能包括&#xff1a; 1. 高速数据传输&#xff1a;百兆集成网络链接器支持100Mbps的数据传输速率&#xff0c;比之前的以太…

河道采砂执法监管信息化平台:科技赋能,智慧监管

随着信息技术的飞速发展&#xff0c;信息化平台已经成为提升行业监管效率和水平的重要工具。河道采砂作为水利资源管理的重要环节&#xff0c;其执法监管同样需要与时俱进&#xff0c;利用先进技术手段提升监管效能。河道采砂执法监管信息化平台便是这一背景下的产物&#xff0…

某酒业集团数字化转型规划(169页附下载)

某酒业集团数字化转型项目实施方案建议书(P169).rar是一个极具参考价值的资料&#xff0c;它详细地阐述了如何利用数字化技术来推动企业转型。这份建议书以IBM的先进技术和某酒业集团的实际应用需求为基础&#xff0c;提出了一套全面、系统的数字化转型解决方案。该方案首先对某…

在linux系统打开pycharm,为pycharm在桌面设置图标

1.打开终端输入&#xff1a;gedit /usr/share/applications/Pycharm.desktop 然后会弹出一个文件 2.在文件中写入&#xff1a; [Desktop Entry] TypeApplication NamePycharm GenericNamePycharm3 CommentPycharm3:The Python IDE Execsh /home/.../pycharm.sh #自己pych…

【kettle002】kettle访问人大金仓KingbaseES数据库并处理数据至execl文件

一直以来想写下基于kettle的系列文章&#xff0c;作为较火的数据ETL工具&#xff0c;也是日常项目开发中常用的一款工具&#xff0c;最近刚好挤时间梳理、总结下这块儿的知识体系。 熟悉、梳理、总结下人大金仓KingbaseES数据库相关知识体系 kettle访问人大金仓KingbaseES数据库…

Centos之yum安装好玩的命令

1.会动的小火车 我在root下使用的 yum install sl.x86_64sl2.figlet yum install figlet.x86_64figlet 55553.cowsay会说话 yum install cowsay

javaScript基础3

javaScript 一.对象1.概念2.创建对象的三种方法(1).字面量创建&#xff08;利用{}&#xff09;(2)变量、属性、函数、方法的区别(3).new Object创建(4).构造函数 3.new关键字的执行过程4.遍历对象&#xff08;for..in) 二.内置对象1.了解2.math对象3.日期对象&#xff08;构造函…

【声呐仿真】学习记录0.5-配置ssh远程连接docker、在docker中使用nvidia显卡

【声呐仿真】学习记录0.5-配置ssh远程连接docker、在docker中使用nvidia显卡 配置ssh远程连接docker1.端口映射2.配置ssh 在docker中使用nvidia显卡配置CUDA 注意&#xff1a;之前已经创建过容器的&#xff0c;需要打包成镜像&#xff0c;重新创建容器&#xff0c;因为要在创建…

伐木机不要石头!!!

伐木机不要石头&#xff01;&#xff01;&#xff01;(easy version) 本题有对应的hard version&#xff0c;区别仅在多次询问中。保证easy version的测试用例集是hard version的真子集&#xff0c;通过困难版本的代码经过简单修改可直接通过简单版 看着家里贫瘠的资源&#x…

【Python学习】面向对象

面向对象 1.初识对象1.1 生活中数据的组织1. 2 程序中数据的组织1.3 使用对象组织数据1.4进行对比 2. 成员方法2.1 类的定义和使用2.2 成员变量和成员方法2.2.1 成员变量2.2.2 成员方法的定义语法2.2.3 self 的作用 3. 类和对象3.1 面向过程3.2 面向对象 4.构造方法4.1 属性成员…

用Vue做一个待办事项

这个待办事项有以下功能&#xff1a;增删查&#xff0c;既新增待办事项&#xff0c;删除待办事项&#xff0c;查看全部&#xff0c;未完成&#xff0c;完成待办事项&#xff0c;当鼠标移动到待办事项上时会显示删除按钮 分为四个部分来实现&#xff1a;ToDoHeader.vue、ToDoMai…

XYCTF 部分wp及学习记录

1.ezmd5 根据题目提示 我们知道应该是要上传两张md5值相同的图片 根据原文链接&#xff1a;cryptanalysis - Are there two known strings which have the same MD5 hash value? - Cryptography Stack Exchange 把保存下来的图片上传一下 得到flag 2.ezhttp 根据原文链接&…