当前位置: 首页 > news >正文

【递归、搜索与回溯】DFS解决FloodFill算法

一、经验总结

之前我们已经研究过了BFS解决FloodFill算法:【优选算法】BFS解决FloodFill算法-CSDN博客

DFS只是遍历顺序发生了变化,其他需要注意的点大差不差。


二、相关编程题

2.1 图像渲染

题目链接

733. 图像渲染 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

以给定的初始坐标为起点开始进行DFS,将遍历到的每个位置都修改为新的颜色值(可以防止重复遍历)。需要注意的是,如果修改前后的颜色值相同则会出现重复遍历以至于死循环的结果,所以要进行特殊处理。

编写代码

class Solution {int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int m, n, oldcolor, newcolor;
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();newcolor = color, oldcolor = image[sr][sc];image[sr][sc] = newcolor;DFS(image, sr, sc);return image;}void DFS(vector<vector<int>>& image, int sr, int sc){for(int i = 0; i < 4; ++i){int x=sr+dx[i], y = sc+dy[i];if(x>=0 && x<m && y>=0 && y<n && image[x][y]==oldcolor){image[x][y] = newcolor;DFS(image, x, y);}}}
};

2.2 岛屿数量

题目链接

200. 岛屿数量 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

遍历grid数组,当遇到未访问的陆地时:

  1. 统计岛屿数量
  2. 以该位置为起点进行深度优先遍历,遍历整个连通块
  3. 将整个连通块中的所有陆地都标记为已访问

编写代码

class Solution {int m, n, ret;vector<vector<bool>> visited;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();visited.resize(m, vector<bool>(n, false));for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(grid[i][j]=='1' && !visited[i][j]){++ret;DFS(grid, i, j);}}}return ret;}void DFS(vector<vector<char>>& grid, int r, int c){visited[r][c] = true;for(int i = 0; i < 4; ++i){int x=r+dx[i], y=c+dy[i];if(x>=0 && x<m && y>=0 && y<n && grid[x][y]=='1' && !visited[x][y]){DFS(grid, x, y);}}}
};

2.3 岛屿的最大面积

题目链接

695. 岛屿的最大面积 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

同上一题基本相同,之不过需要多添加一个变量用于统计每个岛屿的面积。最终返回岛屿的最大面积。

编写代码

class Solution {int m, n, ret, tmp;vector<vector<bool>> visited;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();visited.resize(m, vector<bool>(n, false));for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(grid[i][j]==1 && !visited[i][j]){tmp = 0;DFS(grid, i, j);ret = max(tmp, ret);}}}return ret;}void DFS(vector<vector<int>>& grid, int r, int c){++tmp;visited[r][c] = true;for(int i = 0; i < 4; ++i){int x=r+dx[i], y=c+dy[i];if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1 && !visited[x][y]){DFS(grid, x, y);}}}
};

2.4 被围绕的区域

题目链接

130. 被围绕的区域 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
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 j = 0; j < n; ++j){if(board[0][j] == 'O') DFS(board, 0, j);if(board[m-1][j] == 'O') DFS(board, m-1, j);}for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(board[i][j] == 'O') board[i][j] = 'X';if(board[i][j] == '.') board[i][j] = 'O';}}}void DFS(vector<vector<char>>& board, int r, int c){board[r][c] = '.';for(int i = 0; i < 4; ++i){int x=r+dx[i], y=c+dy[i];if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O'){DFS(board, x, y);}}}
};

2.5 太平洋大西洋水流问题

题目链接

417. 太平洋大西洋水流问题 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

  1. 统计太平洋水流:以紧邻太平洋的水域(第一行和第一列)为起点逆着水流的方向(>=)进行深度优先遍历,将DFS访问过的水域标记在pacific哈希表。
  2. 统计大西洋水流:以紧邻大西洋的水域(最后一行和最后一列)为起点逆着水流的方向(>=)进行深度优先遍历,将DFS访问过的水域标记在atlantic哈希表。
  3. 找到太平洋和大西洋水流的交集,返回结果。

编写代码

class Solution {int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};vector<vector<bool>> pacific;vector<vector<bool>> atlantic;
public:vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {m = heights.size(), n = heights[0].size();pacific.resize(m, vector<bool>(n, false));atlantic.resize(m, vector<bool>(n, false));vector<vector<int>> ret;for(int i = 0; i < m; ++i){if(!pacific[i][0]) DFS(heights, pacific, i, 0);if(!atlantic[i][n-1]) DFS(heights, atlantic, i, n-1);}for(int j = 0; j < n; ++j){if(!pacific[0][j]) DFS(heights, pacific, 0, j);if(!atlantic[m-1][j]) DFS(heights, atlantic, m-1, j);}for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(pacific[i][j] && atlantic[i][j]){ret.push_back({i, j});}}}return ret;}void DFS(vector<vector<int>>& heights, vector<vector<bool>>& ocean, int r, int c){ocean[r][c] = true;for(int i = 0; i < 4; ++i){int x=r+dx[i], y=c+dy[i];if(x>=0 && x<m && y>=0 && y<n && !ocean[x][y] && heights[x][y]>=heights[r][c]){DFS(heights, ocean, x, y);}}}
};

2.6 扫雷游戏

题目链接

529. 扫雷游戏 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

见代码

编写代码

class Solution {//注意:有8个方向的向量int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1}; int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};int m, n;
public:vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {int sr = click[0], sc = click[1];if(board[sr][sc] == 'M') //点中雷直接返回{board[sr][sc] = 'X';return board;}m = board.size(), n = board[0].size();DFS(board, sr, sc);return board;}void DFS(vector<vector<char>>& board, int r, int c){//统计点击位置周围的地雷数量int cnt = 0;for(int i = 0; i < 8; ++i){int x=r+dx[i], y=c+dy[i];if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M')++cnt;}if(cnt == 0) //周围没有地雷,向四周继续拓展{board[r][c] = 'B';for(int i = 0; i < 8; ++i){int x=r+dx[i], y=c+dy[i];if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='E')DFS(board, x, y);}}else //周围有地雷,标记周围地雷的数量board[r][c] = cnt+'0';}
};

2.7 衣橱整理

题目链接

LCR 130. 衣橱整理 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

编写代码

class Solution {int ret;int _m, _n, _cnt;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool visited[100][100];
public:int wardrobeFinishing(int m, int n, int cnt) {_m = m, _n = n, _cnt = cnt;DFS(0, 0);return ret;}void DFS(int r, int c){visited[r][c] = true;++ret;for(int i = 0; i < 4; ++i){int x=r+dx[i], y=c+dy[i];if(x>=0 && x<_m && y>=0 && y<_n && !visited[x][y] && digit(x)+digit(y)<=_cnt)DFS(x, y);}}int digit(int num){int sum = 0;while(num > 0){sum+=num%10;num/=10;}return sum;}
};

相关文章:

【递归、搜索与回溯】DFS解决FloodFill算法

一、经验总结 之前我们已经研究过了BFS解决FloodFill算法&#xff1a;【优选算法】BFS解决FloodFill算法-CSDN博客 DFS只是遍历顺序发生了变化&#xff0c;其他需要注意的点大差不差。 二、相关编程题 2.1 图像渲染 题目链接 733. 图像渲染 - 力扣&#xff08;LeetCode&am…...

【Spine学习12】之 事件帧

1、新建事件帧&#xff1a; 2、选择第8s的攻击帧&#xff0c;点击第一步新建的attack事件帧前面的钥匙 这样每次动作到8s的时候会自动跳出事件帧提示 这个文字实际动画不会显示 事件是动画过程中所发生情况的触发器。 给程序员识别的...

【C语言习题】31.冒泡排序

文章目录 作业标题作业内容2.解题思路3.具体代码 作业标题 冒泡排序 作业内容 实现一个对整形数组的冒泡排序 2.解题思路 先了解一下冒泡排序&#xff1a; 两两相邻的元素进行比较&#xff0c;如果前面元素大于后面元素就交换两个元素的位置&#xff0c;最终的结果是最大的…...

【Spring Cloud应用框架】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…...

Repetition Improves Language Model Embeddings论文阅读笔记

文章提出了一种提高decoder-only LLM的embedding能力的方法&#xff0c;叫echo embeddingslast-token pooling&#xff08;即直接选最后一个token作为句子的embedding&#xff09;和直接mean pooling都不如文章提出的echo embedding&#xff0c;做法是把句子重复两次&#xff0…...

工具清单 - Bug追踪管理

# 工具清单 Bugzilla在新窗口打开 - General-purpose bugtracker and testing tool originally developed and used by the Mozilla project. MPL-2.0 PerlBumpy Booby在新窗口打开 - Simple, responsive and highly customizable PHP bug tracking system. (Source Code在新窗…...

企业内网是如何禁用U盘的?电脑禁用U盘有哪些方法?

在当今企业环境中&#xff0c;数据安全和信息保护至关重要。 为了防止数据泄露和恶意软件传播&#xff0c;很多企业选择在内网中禁用U盘&#xff0c;以控制数据的物理传输。 小编这就来给大家总结一份详细指南&#xff01;&#xff01; 关于企业内网如何禁用U盘的指南&#x…...

怎样打印微信文档文件?

在日常生活和工作中&#xff0c;我们经常需要打印微信中的文档文件&#xff0c;无论是工作资料、学习笔记还是其他重要信息。随着科技的发展&#xff0c;我们不再需要前往打印店进行繁琐的操作&#xff0c;而是可以通过一些便捷的在线打印平台轻松实现。今天&#xff0c;我们就…...

【讲解下Pip换源】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…...

分享:2024年(第12届)“泰迪杯”数据挖掘挑战赛省级奖项获奖名单公示

本次竞赛有评选省奖的省份有广东省、广西壮族自治区、河北省、湖北省。各省奖项依据“泰迪杯”全国评审专家组统一评阅的最终成绩区分省份后从高到低依序按比例产生。 广东省 省级奖项获奖名单公示 奖项设置&#xff1a; 一等奖&#xff1a;约占该省份队伍总数的5%&#xff0…...

后端开发中缓存的作用以及基于Spring框架演示实现缓存

缓存的作用及演示 现在我们使用的程序都是通过去数据库里拿数据然后展示的 长期对数据库进行数据访问 这样数据库的压力会越来越大 数据库扛不住了 创建了一个新的区域 程序访问去缓存 缓存区数据库 缓存里放数据 有效降低数据访问的压力 我们首先进行一个演示 为了演示…...

Redis原理篇——分布式锁

Redis原理篇——分布式锁 分布式锁是什么&#xff1f;分布式锁有哪些特性&#xff1f;分布式锁常用实现方式Redis 实现分布式锁一、简单的 Redis 锁二、带过期时间的 Redis 锁三、加上 Owner 的 Redis 锁四、Lua 脚本确保原子性 分布式锁是什么&#xff1f; 分布式锁是在分布式…...

css3多列布局

css3多列布局 colmns属性 columns属性是一个简写属性 column-count属性&#xff1a;定义列的数量或者允许的最大列数 auto 为默认值&#xff0c;用于表示列的数量由其他css属性决定number 必须是正整数&#xff0c;用于定义列数量 column-width属性&#xff1a;定义列的宽度 …...

Java开发的构建神器:Maven以及如何安装部署Maven

目录 一、Maven引言1.1 Maven的核心概念✍. POM (Project Object Model)✌. 依赖管理✍. 生命周期与构建阶段✌. 插件系统 1.2 Maven的工作流程✍. 读取POM文件&#xff1a;✌. 依赖解析&#xff1a;✍. 构建生命周期&#xff1a;✌. 插件执行&#xff1a;✍. 构建输出&#xf…...

echarts学习:使用dataset管理数据

前言 在我们公司的组件库中有许多echarts图表相关的组件&#xff0c;这些组件在使用时&#xff0c;只需将图表数据以特定的格式传入组件中&#xff0c;十分方便。因此当我得知echarts 可以使用dataset集中管理数据时&#xff0c;我就决定自己一定要搞懂它&#xff0c;于是在最…...

MyBatis逆向工程和MyBatisX插件的使用

文章目录 1.ORM思维2.逆向工程3.MyBatisX插件的使用 1.ORM思维 ORM&#xff08;Object-Relational Mapping&#xff0c;对象-关系映射&#xff09;是一种将数据库和面向对象编程语言中的对象之间进行转换的技术。它将对象和关系数据库的概念进行映射&#xff0c;最后我们就可以…...

探索C嘎嘎的奇妙世界:第十四关---STL(string的模拟实现)

1. string类的模拟实现 1.1 经典的string类问题 上一关已经对string类进行了简单的介绍&#xff0c;大家只要能够正常使用即可。在面试中&#xff0c;面试官总喜欢让学生自己来模拟实现string类&#xff0c;最主要是实现string类的构造、拷贝构造、赋值运算符重载以及析构函数…...

【JavaScript脚本宇宙】玩转图像处理:从基础到高级,这些库你不能错过!

让你的网页图像栩栩如生&#xff1a;六种必备图像处理库 前言 在数字图像处理中&#xff0c;我们经常需要对图片进行各种操作&#xff0c;如调整亮度、对比度、饱和度等&#xff0c;以达到所需的效果。为了简化这些操作并提供更丰富的功能&#xff0c;出现了许多专门用于图像…...

python+unity手势控制地球大小

效果图如下 具体操作如下 1 在unity窗口添加一个球体 2 给球体添加材质,材质图片使用地球图片 地球图片如下 unity材质设置截图如下 3 编写地球控制脚本 using System.Collections; using System.Collections.Generic; using UnityEngine;public class test : MonoBehavio…...

CSS【实战】抽屉动画

效果预览 技术要点 实现思路 元素固定布局&#xff08;fixed&#xff09;在窗口最右侧外部js 定时器改变元素的 right 属性&#xff0c;控制元素移入&#xff0c;移出 过渡动画 transition transition: 过渡的属性 过渡的持续时间 过渡时间函数 延迟时间此处改变的是 right …...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...