关于【网格结构】岛屿类问题的通用解法DFS(深度遍历)遍历框架+回溯+剪枝总结
最近在刷力扣时遇见的问题,自己总结加上看了力扣大佬的知识总结写下本篇文章,我们所熟悉的 DFS(深度优先搜索)问题通常是在树或者图结构上进行的。而我们今天要讨论的 DFS 问题,是在一种「网格」结构中进行的。岛屿问题是这类网格 DFS 问题的典型代表。网格结构遍历起来要比二叉树复杂一些,如果没有掌握一定的方法,DFS 代码容易写得冗长繁杂。
目录
一、网格类问题的DFS遍历方法
1.1网格问题基本概念
1.2 DFS的基本结构
1.3 如何避免重复遍历
二、岛屿经典例题
2.1 岛屿数量
2.2 岛屿的周长
2.3 单词搜索
一、网格类问题的DFS遍历方法
1.1网格问题基本概念
网格问题是由 m×n 个小方格组成一个网格,每个小方格与其上下左右四个方格认为是相邻的,要在这样的网格上进行某种搜索。岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。 数字为1的格子连接起来就形成一个岛屿。
1.2 DFS的基本结构
首先我们要确定访问的下一个节点以及停止的边界,那么首先网格结构中的每个格子可以向四周延伸,分别为上,下,左,右,对于格子(r,c)来说,对应的四个坐标分别为(r+1,c)、(r-1,c)、(r,c-1)、(r,c+1)。
其次超出格子的边界是什么?是grid[r][c]出现下标越界异常的格子,也就是那些超出范围的格子。
这样我们就得到了网格DFS遍历的框架代码:
public void infect(char[][] grid,int i ,int j){
//超出范围if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){return;}
//访问上,下,左,右infect(grid,i+1,j);infect(grid,i-1,j);infect(grid,i,j+1);infect(grid,i,j-1);
}
1.3 如何避免重复遍历
网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于,遍历中可能遇到遍历过的结点。这是因为,网格结构本质上是一个「图」,我们可以把每个格子看成图中的结点,每个结点有向上下左右的四条边。在图中遍历时,自然可能遇到重复遍历结点。
如何避免这样的重复遍历呢?答案是将已经遍历过的格子的值修改一下,每次走过一个格子就修改格子的值。以岛屿问题为例,我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子,就把格子的值改为 2,这样当我们遇到 2 的时候,就知道这是遍历过的格子了。
public void infect(char[][] grid,int i ,int j){if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length ){return;}grid[i][j] = '2';infect(grid,i+1,j);infect(grid,i-1,j);infect(grid,i,j+1);infect(grid,i,j-1);}
二、岛屿经典例题
2.1 岛屿数量
岛屿类问题的通用解法、DFS 遍历框架 - 岛屿数量 - 力扣(LeetCode)
- 0 —— 海洋格子
- 1 —— 陆地格子(未遍历过)
- 2 —— 陆地格子(已遍历过)
class Solution {public int numIslands(char[][] grid) {int islandNum = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == '1'){infect(grid,i,j);islandNum++;}}}return islandNum;}public void infect(char[][] grid,int i ,int j){if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1'){return;}grid[i][j] = '2';infect(grid,i+1,j);infect(grid,i-1,j);infect(grid,i,j+1);infect(grid,i,j-1);}
}
2.2 岛屿的周长
463. 岛屿的周长 - 力扣(LeetCode)
给你一个由
'1'
(陆地)和'0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。
我们可以将岛屿的周长中的边分为两类,如下图所示。黄色的边是与网格边界相邻的周长,而蓝色的边是与海洋格子相邻的周长。
当我们的 dfs 函数因为「坐标 (r, c) 超出网格范围」返回的时候,实际上就经过了一条黄色的边;而当函数因为「当前格子是海洋格子」返回的时候,实际上就经过了一条蓝色的边。
本题我们可以再次嵌套DFS的框架,但是要增加几处地方,实际上,岛屿的周长是计算岛屿全部的「边缘」,而这些边缘就是我们在 DFS 遍历中,
dfs
函数返回的位置。
class Solution {public int islandPerimeter(int[][] grid) {for (int r = 0; r < grid.length; r++) {for (int c = 0; c < grid[0].length; c++) {if (grid[r][c] == 1){return dfs(grid,r,c);}}}return 0;}public int dfs(int[][] grid,int r,int c){if (r < 0 || r >= grid.length ||c < 0 || c >= grid[0].length ){return 1;}if (grid[r][c] == 0){return 1;}if (grid[r][c] != 1){return 0;}grid[r][c] = 2;return dfs(grid,r-1,c)+dfs(grid,r+1,c)+dfs(grid,r,c-1)+dfs(grid,r,c+1);}
}
2.3 单词搜索
79. 单词搜索 - 力扣(LeetCode)
给定一个
m x n
二维字符网格board
和一个字符串单词word
。如果word
存在于网格中,返回true
;否则,返回false
。
本题在使用上面的DFS框架时,要加上回溯,因为当搜索一次时,会更改当前的格子的值,
如果我在DFS的过程中不改矩阵的状态,那我就会出现重复搜索的情况啊,这可不行,因此矩阵是必须得改的。那就只剩下一个办法了,每次DFS的过程中修改矩阵,DFS完了再把矩阵给改回去呗,这就是回溯!
那么什么是剪枝呢?所谓剪枝就是我在dfs的时候,如果已经找到一个正确的路径了,换句话说已经得到结果了,其实就没必要继续DFS了,直接返回结果即可。这就是剪枝。
给一下官方的说法:剪枝,就是减小树的规模,尽早排除搜索树中不必要的分支的一种手段。
class Solution {private boolean find;public boolean exist(char[][] board, String word) {if(board == null){return false;}int m = board.length,n = board[0].length;boolean[][] visited = new boolean[m][n];find = false;for(int i = 0;i < m;i++){for(int j = 0 ;j < n;j++){backtracking(i, j, board, word, visited, 0);}}return find;}/*** i,j,board:棋盘格及当前元素的坐标* word: 要搜索的目标单词* visited:记录当前格子是否已被访问过* pos: 记录目标单词的字符索引,只有棋盘格字符和pos指向的字符一致时,才有机会继续搜索接下来的字符;如果pos已经过了目标单词的尾部了,那么便说明找到目标单词了*/public void backtracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos){// 超出边界、已经访问过、已找到目标单词、棋盘格中当前字符已经和目标字符不一致了if(i < 0 || i >= board.length || j <0 || j>=board[0].length || visited[i][j] || find || board[i][j] != word.charAt(pos)){return;}if(pos == word.length()-1){find = true;return;}visited[i][j] = true;// 修改当前节点状态backtracking(i+1, j, board, word, visited, pos+1); // 遍历子节点backtracking(i-1, j, board, word, visited, pos+1);backtracking(i, j+1, board, word, visited, pos+1);backtracking(i, j-1, board, word, visited, pos+1);visited[i][j] = false; // 撤销修改}
}
如果对你有帮助,麻烦双击三连一下,谢谢啦!
相关文章:

关于【网格结构】岛屿类问题的通用解法DFS(深度遍历)遍历框架+回溯+剪枝总结
最近在刷力扣时遇见的问题,自己总结加上看了力扣大佬的知识总结写下本篇文章,我们所熟悉的 DFS(深度优先搜索)问题通常是在树或者图结构上进行的。而我们今天要讨论的 DFS 问题,是在一种「网格」结构中进行的。岛屿问题…...

【LeetCode】982. 按位与为零的三元组
982. 按位与为零的三元组 题目描述 给你一个整数数组 nums ,返回其中 按位与三元组 的数目。 按位与三元组 是由下标 (i, j, k) 组成的三元组,并满足下述全部条件: 0 < i < nums.length0 < j < nums.length0 < k < num…...

Linux内核源码进程原理分析
Linux内核源码进程原理分析一、Linux 内核架构图二、进程基础知识三、Linux 进程四要素四、task_struct 数据结构主要成员五、创建新进程分析六、剖析进程状态迁移七、写时复制技术一、Linux 内核架构图 二、进程基础知识 Linux 内核把进程称为任务(task),进程的虚…...

电子技术——CMOS反相器
电子技术——CMOS反相器 在本节,我们深入学习CMOS反相器。 电路原理 下图是我们要研究的CMOS反相器的原理图: 下图展示了当输入 vIVDDv_I V_{DD}vIVDD 时的 iD−vDSi_D-v_{DS}iD−vDS 曲线: 我们把 QNQ_NQN 当做是驱动源&#x…...
gazebo仿真轨迹规划+跟踪(不在move_base框架下)
以Tianbot为例子,开源代码如下: https://github.com/tianbot/tianbot_mini GitHub - tianbot/abc_swarm: Ant Bee Cooperative Swarm, indicating air-ground cooperation. This repository is for Tianbot Mini and RoboMaster TT swarm kit. 1.在…...

C. Good Subarrays(前缀和)
C. Good Subarrays一、问题二、分析三、代码一、问题 二、分析 这道题目的意思就是给我们一个数组,然后我们从数组中选取一个连续的区间,这个区间满足条件:区间内的元素和等于区间的长度。 对于区间和问题我们先想到的是前缀和的算法。 那…...

关于Facebook Messenger CRM,这里有你想要知道的一切
关于Facebook Messenger CRM,这里有你想要知道的一切!想把Facebook Messenger与你的CRM整合起来吗?这篇博文是为你准备的! 我们将介绍有关获得Facebook Messenger CRM整合的一切信息。然后,我们将解释为什么你需要像SaleSmartly&a…...

ChIP-seq 分析:数据与Peak 基因注释(10)
动动发财的小手,点个赞吧! 1. 数据 今天,我们将继续回顾我们在上一次中研究的 Myc ChIPseq。这包括用于 MEL 和 Ch12 细胞系的 Myc ChIPseq。 可在此处[1]找到 MEL 细胞系中 Myc ChIPseq 的信息和文件可在此处[2]找到 Ch12 细胞系中 Myc ChIP…...
《C++ Primer Plus》第18章:探讨 C++ 新标准(8)
使用大括号括起的初始化列表语法重写下述代码。重写后的代码不应使用数组 ar: class Z200 { private:int j;char ch;double z; public:Z200(int jv, char chv, zv) : j(jv), ch(chv), z(zv) {} ... };double x 8.8; std::string s "What a bracing effect!&q…...

YOLO-V5 系列算法和代码解析(八)—— 模型移植
文章目录工程目标芯片参数查阅官方文档基本流程Python 版工具链安装RKNPU2的编译以及使用方法移植自己训练的模型工程目标 将自己训练的目标检测模型【YOLO-V5s】移植到瑞芯微【3566】芯片平台,使用NPU推理,最终得到正确的结果。整个过程涉及模型量化、…...
js实现复制拷贝的兼容方法
1. 定义复制拷贝的方法 在某个工具类方法中定义该方法,兼容不同浏览器处理 /*** description 拷贝的类方法*/ class CopyClass {// constructor() {}setRange(input) {return new Promise((resolve, reject) > {try {// 创建range对象const range document.c…...

学习 Python 之 Pygame 开发魂斗罗(八)
学习 Python 之 Pygame 开发魂斗罗(八)继续编写魂斗罗1. 创建敌人类2. 增加敌人移动和显示函数3. 敌人开火4. 修改主函数5. 产生敌人6. 使敌人移动继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗(七)中࿰…...

Lesson11---分类问题
11.1 逻辑回归 11.1.1 广义线性回归 课程回顾 线性回归:将自变量和因变量之间的关系,用线性模型来表示;根据已知的样本数据,对未来的、或者未知的数据进行估计 11.1.2 逻辑回归 11.1.2.1 分类问题 分类问题:垃圾…...
Python基础学习12——异常
在Python中,会使用“异常”这个十分特殊的对象来管理程序执行期间发生的错误,即报错。本文将介绍一下python基础的处理异常的方法以及一些基本的异常类型。 异常处理方法 try-except代码块 当我们编写程序时,我们可以编写一个try-except代…...
[日常练习]练习17:链表头插法、尾插法练习
[日常练习]练习17:链表头插法、尾插法练习练习17描述输入输出输入示例1输出示例1输入示例2输出示例2代码演示:总结练习17 【日常练习】 链表头插法、尾插法练习 描述 输入3 4 5 6 7 9999一串整数,9999代表结束,通过头插法新建链…...

第十四届蓝桥杯模拟赛(第三期)试题与题解 C++
目录 一、填空题 (一)最小的十六进制(答案:2730) (二)Excel的列(答案:BYT) (三)相等日期(答案:70910) (四)多少种取法(答案:189)…...
关于 “宏“
起源 宏 Macro"这个词源于希腊语 “makros”,意为“大的,长的” 延伸使用 随后用于计算机领域是,在汇编语言时用于描述一大堆的汇编指令。 只要用宏指令,就是直接用的一大堆的汇编指令(有点函数的味道…...

1.2 CSS标签选择器,类选择器
CSS选择器: 根据不同的需求选出不同的标签,进行美化装饰 1. 标签选择器 标签选择器(元素选择器):用 HTML标签名作为选择器,按标签名称进行分类,为页面某一类标签指定统一的CSS样式 作用: 可以把某一类标签全部选中&…...

【Linux】进程等待 | 详解 wait/waitpid 的 status 参数
🤣 爆笑教程 👉 《看表情包学Linux》👈 猛戳订阅 🔥 💭 写在前面:在上一章中我们讲解了进程创建与进程终止,本章我们开始讲解进程等待。进程等待这部分知识相较于前面还是较为复杂的࿰…...
OpenAI眼中的无线调优策略
问:无线调优策略该怎么优化无线调优是指对无线网络的各种参数进行优化,以提高网络性能和用户体验。以下是几个无线调优策略:频谱分配:通过优化频谱的分配,可以提高网络的容量和覆盖范围。在频谱分配时,需要…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...