FloodFill 算法(DFS)
文章目录
- FloodFill 算法(DFS)
- 图像渲染
- 岛屿数量
- 岛屿的最大面积
- 被围绕的区域
- 太平洋大西洋水流问题
- 扫雷游戏
- 衣橱整理
FloodFill 算法(DFS)
漫水填充(Flood Fi)算法是一种图像处理算法,在计算机图形学和计算机视觉中被广泛应用。它用于填充图像中的连通区域,从一个种子点开始,沿着相邻的像素进行填充操作,直到达到某个停止条件为止。该算法可以实现图像填充、颜色替换、图像分割等操作。
图像渲染
题目:图像渲染

思路
从起点开始深度优先搜索,当遇到上下左右和当前一样时,即为合法目标,将其修改为
color,用一个标记数组visited来判断当前位置是否访问过
C++代码
class Solution
{bool visited[51][51];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0}; int m, n;int prev;
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {if(image[sr][sc] == color) return image;m = image.size(), n = image[0].size();prev = image[sr][sc];visited[sr][sc] = true;dfs(image, sr, sc, color);visited[sr][sc] = false;return image;}void dfs(vector<vector<int>>& image, int i, int j, int color){image[i][j] = color;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(0 <= x && x < m && 0 <= y && y < n && !visited[x][y] && image[x][y] == prev){visited[x][y] = true;dfs(image, x, y, color);visited[x][y] =false;}}}
};
岛屿数量
题目:岛屿数量

思路
遍历数组,找到1开始搜索,搜索一次答案++,遍历过后用一个标记数组
visited标记该位置
C++代码
class Solution
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;bool visited[301][301];
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(!visited[i][j] && grid[i][j] == '1'){ret++;dfs(grid, i, j);}}return ret;}void dfs(vector<vector<char>>& grid, int i, int j){visited[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(0 <= x && x < m && 0 <=y && y < n && !visited[x][y] && grid[x][y] == '1'){dfs(grid, x, y);}}}
};
岛屿的最大面积
题目:岛屿的最大面积

思路
和
岛屿数量解题思路一样,只不过在每次遍历岛屿的时候,用一个变量count来统计当前岛屿的大小,并变量完当前岛屿后,和之前最大的结果ret取一个最大值
C++代码
class Solution
{bool visited[51][51];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;int count;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(!visited[i][j] && grid[i][j] == 1){count = 0;dfs(grid, i, j);ret = max(ret, count);}return ret;}void dfs(vector<vector<int>>& grid, int i, int j){visited[i][j] = true;count++;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(0 <= x && x < m && 0 <=y && y < n && !visited[x][y] && grid[x][y] == 1){dfs(grid, x, y);}}}
};
被围绕的区域
题目:被围绕的区域

思路
和
岛屿数量解题思路一样,只不过在每次遍历岛屿的时候,用一个变量count来统计当前岛屿的大小,并变量完当前岛屿后,和之前最大的结果ret取一个最大值
C++代码
class Solution
{int dx[4] = {0,0,1,-1};int dy[4] = {-1,1,0,0};int m, n;
public:void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();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);}for(int i = 1; i < n - 1; i++){if(board[0][i] == 'O') dfs(board, 0, i);if(board[m - 1][i] == 'O') dfs(board, m - 1, i);}for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(board[i][j] == '.') board[i][j] = 'O';else if(board[i][j] == 'O') board[i][j] = 'X'; }}void dfs(vector<vector<char>>& board, int i, int j){board[i][j] = '.';for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(0 <= x && x < m && 0 <= y && y < n && board[x][y] == 'O'){dfs(board, x, y);}}}
};
太平洋大西洋水流问题
题目:太平洋大西洋水流问题

思路
- 对于太平洋边界(即第一行和第一列)上的每个单元格,将其标记为可达太平洋
toPO = true,并将其加入队列进行DFS。在DFS过程中,如果当前单元格的相邻单元格高度不低于当前单元格,且未被标记为可达太平洋,则将其标记为可达太平洋,并加入队列继续搜索 - 对于大西洋边界(即最后一行和最后一列)上的每个单元格,进行类似的操作,将其标记为可达大西洋
toAO= true - 遍历整个矩阵,对于每个单元格,如果它同时被标记为可达太平洋和可达大西洋
toPO && toAO,则将其坐标加入结果列表。
C++代码
class Solution
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;bool toPO[201][201];bool toAO[201][201];vector<vector<int>> ret;
public:vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {m = heights.size(), n = heights[0].size();// 左、上for(int i = 0; i < m; i++) dfs(heights, i, 0, toPO);for(int i = 0; i < n; i++) dfs(heights, 0, i, toPO);// 右、下for(int i = 0; i < m; i++) dfs(heights, i, n - 1, toAO);for(int i = 0; i < n; i++) dfs(heights, m - 1, i, toAO);for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(toPO[i][j] && toAO[i][j]) ret.push_back({i, j});return ret;}void dfs(vector<vector<int>>& heights, int i, int j, bool visited[201][201]){visited[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(0 <= x && x < m && 0 <= y && y < n && !visited[x][y] && heights[x][y] >= heights[i][j])dfs(heights, x, y, visited);}}
};
扫雷游戏
题目:扫雷游戏

思路
理解题目意思,模拟+深度优先搜索
C++代码
class Solution
{int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};int dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};int m, n;
public:vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click){ m = board.size(), n = board[0].size();int x = click[0], y = click[1];if(board[x][y] == 'M'){board[x][y] = 'X';return board;}dfs(board, x, y);return board;}void dfs(vector<vector<char>>& 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(0 <= x && x < m && 0 <= y && y < n && board[x][y] == 'M'){count++;}}// 周围有地雷if(count){board[i][j] = count + '0';return;}else{board[i][j] = 'B';for(int k = 0; k < 8; k++){int x = i + dx[k], y = j + dy[k];if(0 <= x && x < m && 0 <= y && y < n && board[x][y] == 'E'){dfs(board, x, y);}} }}
};
衣橱整理
题目:衣橱整理

思路
模拟+DFS
C++代码
class Solution
{int ret;bool vis[101][101];int dx[4] = {0, 1};int dy[4] = {1, 0};int m, n, cnt;
public:int wardrobeFinishing(int _m, int _n, int _cnt) {m = _m, n = _n, cnt = _cnt;dfs(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];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x,y)){dfs(x, y);}}}bool check(int i,int j){int tmp = 0;while(i){tmp += i % 10;i /= 10;}while(j){tmp += j % 10;j /= 10;}return tmp <= cnt;}
};
相关文章:
FloodFill 算法(DFS)
文章目录 FloodFill 算法(DFS)图像渲染岛屿数量岛屿的最大面积被围绕的区域太平洋大西洋水流问题扫雷游戏衣橱整理 FloodFill 算法(DFS) 漫水填充(Flood Fi)算法是一种图像处理算法,在计算机图形学和计算机视觉中被广泛…...
计算机通信与网络实验笔记
1.LINUX通过版本号判断是否为稳定版本 2.计网基础 (CD),默认二层以太网交换机。 (10)物理层是均分(除以),数据链路层及以上是不除的。 3.传输介质: (1&…...
闲聊【干龙头】的重要性
市场面临转势,我们不知道谁会先涨,资金量大的操作必然会提前布局,而我们需要做的就是睁大眼睛,等待最强的那只股票出现,然后闭着眼睛进入就可以了。 追涨操作为什么都出现在大盘大涨情况下。原因简单,不能确…...
Ubuntu22.04安装RTX3080
Ubuntu22.04安装RTX3080 1 安装基础环境 更新依赖包 sudo apt-get update sudo apt-get upgrade2 安装驱动 (1)查看适合的显卡驱动 # 查看可用的驱动 sudo ubuntu-drivers devices# 返回值,推荐版本:nvidia-driver-550 ERROR…...
嵌入式学习-IO进程-Day04
嵌入式学习-IO进程-Day04 进程的函数接口 fork和Vfork 回收进程资源 wait waitpid 退出进程 获取进程号(getpid,getppid) 守护进程 守护进程的特点 创建步骤 exec函数族 线程 概念 线程和进程的区别 线程资源 线程函数接口 创建线程ÿ…...
RAII - 安卓中的智能指针
RAII - 安卓中的智能指针 概念 sp wp RefBase 是什么 system/core/libutils/RefBase.cpp system/core/libutils/include/utils/RefBase.hsystem/core/libutils/StrongPointer.cpp system/core/libutils/include/utils/StrongPointer.hAndroid在标准库之外,自定义…...
linux--库指令
ldd ldd 可执行文件路径 显示依赖的库的查找路径以及是否查找到了。...
展讯方案-内置多张开机logo
1. 开机图片的资源存放在logo分区中,这个分区中可以存放一个xx.bmp文件,也可以存放一个bin文件(1logo.bin,包含多张压缩的图片集合) 2.平台代码中logo.bin是由mk_1ogo_img.py脚本打包,具体如下(…...
Stable Diffusion模型资源合集(附整合包)
(模型资源在ComfyUI、WebUI以及ForgeUI中都通用) 之前的Stable Diffusion笔记受到了不少小伙伴的关注,很感谢大家的建议和支持。有很多小伙伴私信我问我一些AI绘画的模型资源在哪来下载,一般来说有两个网站比较常用,分…...
机器学习|Pytorch实现天气预测
机器学习|Pytorch实现天气预测 🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 电脑系统:Windows11 显卡型号:NVIDIA Quadro P620 语言环境:python 3.9.7 编译器&#x…...
【Kuberntes】k8s权限管理
文章目录 权限管理概述核心概念配置RBAC创建Role和ClusterRole创建RoleBinding和ClusterRoleBinding 默认角色和角色绑定权限的实现注意事项 如何在 Kubernetes 中实现 RBAC 的细粒度权限控制?1. Role和ClusterRole2. RoleBinding和ClusterRoleBinding3. 配置RBAC4.…...
C++,STL 033(24.10.15)
内容 queue容器(队列)的常用接口。 代码 #include <iostream> #include <string> #include <queue> // 注意包含queue容器(队列)的头文件using namespace std;class Person { public:string m_Name;int m_Age…...
AdmX_new
0x00前言 因为环境问题,此次靶场都放在vm上。都为NAT模式。 靶机地址: https://download.vulnhub.com/admx/AdmX_new.7z 需要找到两个flag文件。 0x01信息搜集 搜集IP 确认目标IP为172.16.8.131,进一步信息搜集 获取端口开放情况,版本信…...
【python3】函数注解
Python 函数注解 (Function Annotations) Python 函数注解 (Function Annotations)函数注解的基本语法基本语法格式示例 特殊类型注解注解信息的存储与访问函数注解的实际用途注意事项小结 函数注解是 Python 的一种特性,用于为函数的参数和返回值添加 元数据。注解…...
leetcode hot100 之【LeetCode 42. 接雨水】 java实现
LeetCode 42. 接雨水 题目描述 给定一个非负整数数组 height 表示柱状图中每个柱子的高度,请你计算按此排列的柱状图能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面的柱状图可以…...
10月18日,每日信息差
第一、现代汽车集团在上海举办了中国前瞻技术研发中心的发布及启新庆典,宣布成立其全资法人公司 —— 现代前瞻汽车技术开发(上海)有限公司。该中心是集团在海外建立的首个前瞻技术研发中心,专注于自动驾驶、智能座舱、共享出行等…...
Axure科技感元件:打造可视化大屏设计的得力助手
Axure,作为一款专业的原型设计工具,凭借其强大的设计功能、丰富的组件库和灵活的交互能力,成为了许多设计师打造科技感设计的首选工具。其中,Axure科技感元件更是以其独特的魅力和实用性,在数据可视化大屏、登录界面、…...
【模板】最近公共祖先(LCA)倍增
P3379 P3379 【模板】最近公共祖先(LCA) # 【模板】最近公共祖先(LCA) ## 题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 ## 输入格式 第一行包含三个正整数 $N,M,S$&#…...
我的JAVA项目构建
1.Maven maven就是pip 设置maven下载的的jar包位置 换源 下载插件maven-search 配置dependency 2.Tomcat 设置环境变量JAVA_HOME 设置编码方式 方框就是路径的前缀 3.Servlet 新建项目 写一个类继承HttpServlet,复写doGet(应对Get请求),doPost(应对…...
应用层协议 序列化
自定义应用层协议 例子:网络版本计算器 序列化反序列化 序列化:将消息,昵称,日期整合成消息-昵称-日期 反序列化:消息-昵称-日期->消息,昵称,日期 在序列化中,定义一个结构体…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
