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(应对…...
应用层协议 序列化
自定义应用层协议 例子:网络版本计算器 序列化反序列化 序列化:将消息,昵称,日期整合成消息-昵称-日期 反序列化:消息-昵称-日期->消息,昵称,日期 在序列化中,定义一个结构体…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
