FloodFill(洪水灌溉)算法专题——DFS深搜篇

目录

1、图像渲染

1.1 算法原理

1.2 算法代码

2、岛屿数量

2.1 算法原理

2.2 算法代码

3、岛屿的最大面积

3.1 算法原理

3.2 算法代码

4、被围绕的区域

4.1 算法原理

 4.2 算法代码

5、太平洋大西洋水流问题

5.1 算法原理

5.2 算法代码

6、扫雷游戏

6.1 算法原理

6.2 算法代码

7、衣橱整理 （原：面试题 13. 机器人的运动范围 ）

7.1 算法原理

7.2 算法代码

1、图像渲染

. - 力扣（LeetCode）

1.1 算法原理

  • 从(sr,sc)位置开始上下左右暴搜，将区域中符合条件的值修改为color。
  • 细节问题：当 color == image[sr][sc]时，不需修改，直接返回即可。

1.2 算法代码

class Solution {int[] dx, dy;int[][] image;int color;int n, m;int val;public int[][] floodFill(int[][] image_, int sr, int sc, int color_) {if(color_ == image_[sr][sc]) return image_;image = image_;val = image[sr][sc];color = color_;n = image.length;m = image[0].length;dx = new int[]{-1, 1, 0, 0};dy = new int[]{0, 0, -1, 1};image[sr][sc] = color;dfs(sr, sc);return image;}public void dfs(int i, int j) {for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < n && y >= 0 && y < m && image[x][y] == val) {image[x][y] = color;dfs(x, y);}}}
}

2、岛屿数量

. - 力扣（LeetCode）

2.1 算法原理

全局变量：

  1. boolean[][] check;//是否来过
  2. int ret;//返回值
  3. int[] dx;//横坐标上下左右
  4. int[] dy;//纵坐标上下左右

思想：

  • 遍历矩阵，每次来到新的'1'区域，将这个区域中的所有'1'位置做好标记(check置为false)，ret++
  • 返回ret

2.2 算法代码

class Solution {int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] check;int ret;int m, n;public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;check = new boolean[m][n];for(int i = 0; i < m ; i++) {for(int j = 0; j < n; j++) {if(check[i][j] == false && grid[i][j] == '1') {ret++;check[i][j] = true;dfs(grid, i, j);}}}return ret;}public void dfs(char[][] grid, int i, int j) {for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !check[x][y]) {check[x][y] = true;dfs(grid, x, y);}}}
}

3、岛屿的最大面积

. - 力扣（LeetCode）

3.1 算法原理

与上题基本一致，选出面积最大值即可：

  1. 暴搜
  2. count记录每块陆地的最大面积(每次进入dfs，count++)
  3. ret记录所有陆地的最大面积(选出count的最大值)

3.2 算法代码

class Solution {int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] check;int ret;int m, n;int count;public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;check = new boolean[m][n];for(int i = 0; i < m ; i++) {for(int j = 0; j < n; j++) {if(check[i][j] == false && grid[i][j] == 1) {count = 0;check[i][j] = true;dfs(grid, i, j);//统计一块陆地的面积ret = Math.max(ret, count);}}}return ret;}public void dfs(int[][] grid, int i, int j) {count++;       for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !check[x][y]) {check[x][y] = true;dfs(grid, x, y);}}}
}

4、被围绕的区域

. - 力扣（LeetCode）

4.1 算法原理

 本题采用“正难则反”法则，既然我们无法区分边缘区域与内部区域，那么就先对矩阵的边缘区域进行操作：

  1. 对边缘区域的所有'O'区域进行深搜，修改为'.'
  2. 此时边缘区域的'O'已全部修改为'.'，内部区域的'O'仍为'O'
  3. 再遍历整个矩阵，'.'重新修改为'O'(边缘区域的'O')，'O'则修改为'X'(内部区域的'O')

 4.2 算法代码

class Solution {int m, n;int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };public void solve(char[][] board) {m = board.length;n = board[0].length;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//把边缘区域的O置为.if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {board[i][j] = '.';dfs(board, i, j);}}}for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (board[i][j] == 'O')board[i][j] = 'X';else if (board[i][j] == '.')board[i][j] = 'O';}}public void dfs(char[][] board, int i, int j) {for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {board[x][y] = '.';dfs(board, x, y);}}}
}

5、太平洋大西洋水流问题

. - 力扣（LeetCode）

5.1 算法原理

本题仍采用“正难则反”原则：

  1. 从海岸反向记录可流入海洋的位置
  2. 分别标记哪些位置可流入太平洋（boolean[][] pac），可流入则标为true
  3. 分别标记哪些位置可流入大西洋（boolean[][] atl），可流入则标为true
  4. pac、atl中均为true的位置，说明均可流入两大海洋。

5.2 算法代码

class Solution {int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};int m, n;public List<List<Integer>> pacificAtlantic(int[][] heights) {m = heights.length;n = heights[0].length;boolean[][] pac = new boolean[m][n];//标记太平洋可流入的位置boolean[][] atl = new boolean[m][n];//标记大西洋可流入的位置//pacfor(int j = 0; j < n; j++) dfs(heights, 0, j, pac);for(int i = 0; i < m; i++) dfs(heights, i, 0, pac);//atlfor(int j = 0; j < n; j++) dfs(heights, m - 1, j, atl);for(int i = 0; i < m; i++) dfs(heights, i, n - 1, atl);//都可流入的位置List<List<Integer>> ret = new ArrayList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(pac[i][j] && atl[i][j]) {List<Integer> list = new ArrayList<>();list.add(i);list.add(j);ret.add(list);}}}return ret;}public void dfs(int[][] heights, int i, int j, boolean[][] check) {check[i][j] = true;int cur = heights[i][j];for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && heights[x][y] >= cur) {dfs(heights, x, y, check);}}}
}

6、扫雷游戏

. - 力扣（LeetCode）

6.1 算法原理

本题主要节目就是dfs及回溯：如果相邻没有地雷的空方块被挖出，则将其上下左右及四角方向全部递归揭露所有和其相邻的未挖出的方块，直至相邻的方块的周围有地雷，则将周围有地雷的方块标为地雷的数量。

对于斜方向上，我们只需在dx和dy数组上的对应位置上加上相应值即可。

6.2 算法代码

class Solution {char[][] board;int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};int m, n;public char[][] updateBoard(char[][] board_, int[] click) {board = board_;m = board.length;n = board[0].length;int sx = click[0], sy = click[1];char ch = board[sx][sy];if(ch == 'M') {board[sx][sy] = 'X';return board;}if(ch == 'B') return board;dfs(sx, sy);return board;}public void dfs(int i, int j) {int count = 0;for(int k = 0; k < 8; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {count++;}}if(count != 0) {//周围有地雷board[i][j] = (char)(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(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {dfs(x, y);}}}}
}

7、衣橱整理 （原：面试题 13. 机器人的运动范围 ）

. - 力扣（LeetCode）

7.1 算法原理

直接dfs洪水灌溉，需要注意的是:

  1. 每个位置不能重复进入
  2. 横纵下标的每个位的数值之和不能超过cnt

 7.2 算法代码

class Solution {int ret;int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };int m, n;boolean[][] check;public int wardrobeFinishing(int m_, int n_, int cnt) {m = m_;n = n_;check = new boolean[m][n];dfs(0, 0, cnt);return ret;}public void dfs(int i, int j, int cnt) {check[i][j] = true;ret++;for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && isRight(x, y, cnt)) {dfs(x, y, cnt);}}}public boolean isRight(int x, int y, int cnt) {int sum = 0;while (x != 0) {sum += x % 10;x /= 10;}while (y != 0) {sum += y % 10;y /= 10;}return sum <= cnt;}
}

END

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

React学习day07-ReactRouter-抽象路由模块、路由导航、路由导航传参、嵌套路由、默认二级路由的设置、两种路由模式

React学习day07-ReactRouter-抽象路由模块、路由导航、路由导航传参、嵌套路由、默认二级路由的设置、两种路由模式

14、ReactRouter续 &#xff08;2&#xff09;抽象路由模块 1&#xff09;新建page文件夹&#xff0c;存放组件 组件内容&#xff1a; 2&#xff09;新建router文件夹&#xff0c;在其下创建实例 3&#xff09;实例导入&#xff0c;使用 4&#xff09;效果 &#xff08;3&…
阅读更多...
【大数据方案】智慧大数据平台总体建设方案书（word原件）

【大数据方案】智慧大数据平台总体建设方案书（word原件）

第1章 总体说明 1.1 建设背景 1.2 建设目标 1.3 项目建设主要内容 1.4 设计原则 第2章 对项目的理解 2.1 现状分析 2.2 业务需求分析 2.3 功能需求分析 第3章 大数据平台建设方案 3.1 大数据平台总体设计 3.2 大数据平台功能设计 3.3 平台应用 第4章 政策标准保障体系 4.1 政策…
阅读更多...
Day26_0.1基础学习MATLAB学习小技巧总结（26）——数据插值

Day26_0.1基础学习MATLAB学习小技巧总结（26）——数据插值

利用空闲时间把碎片化的MATLAB知识重新系统的学习一遍&#xff0c;为了在这个过程中加深印象&#xff0c;也为了能够有所足迹&#xff0c;我会把自己的学习总结发在专栏中&#xff0c;以便学习交流。 参考书目&#xff1a; 1、《MATLAB基础教程 (第三版) (薛山)》 2、《MATL…
阅读更多...
Java项目——苍穹外卖（二）

Java项目——苍穹外卖（二）

Redis 简介 Redis是一个基于内存的key-value结构数据库 基于内存存储&#xff0c;读写性能高适合存储热点数据&#xff08;热点商品、资讯、新闻&#xff09;企业应用广泛 基础操作 启动 在redis安装目录中打开cmd&#xff0c;输入如上图指令即可启动&#xff0c;按下crtl…
阅读更多...
【图像匹配】基于SIFT算法的图像匹配，matlab实现

【图像匹配】基于SIFT算法的图像匹配，matlab实现

博主简介&#xff1a;matlab图像代码项目合作&#xff08;扣扣&#xff1a;3249726188&#xff09; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 本次案例是基于基于SIFT算法的图像匹配&#xff0c;用matlab实现。 一、案例背景和算法介绍 本…
阅读更多...
es的封装

es的封装

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、类和接口介绍0.封装思想1.es的操作分类 二、创建索引1.成员变量2.构造函数2.添加字段3.发送请求4.创建索引总体代码 三.插入数据四.删除数据五.查询数据 前…
阅读更多...
Linux下root用户共享conda环境给其他用户

Linux下root用户共享conda环境给其他用户

首先可以先用命令查看环境存储位置 conda env list 比如我的root用户的base环境 # conda environments: # base * /usr/local/miniconda3 在root下先给环境添文件夹加普通用户的权限 chmod -R 755 /usr/local/miniconda3 接下来新建一个用户&#xff0…
阅读更多...
Python 课程14-TensorFlow

Python 课程14-TensorFlow

前言 TensorFlow 是由 Google 开发的一个开源深度学习框架&#xff0c;广泛应用于机器学习和人工智能领域。它具有强大的计算能力&#xff0c;能够运行在 CPU、GPU 甚至 TPU 上&#xff0c;适用于从小型模型到大规模生产系统的各种应用场景。通过 TensorFlow&#xff0c;你可以…
阅读更多...
Unity+LeapMotion2的使用

Unity+LeapMotion2的使用

开始吧 导入步骤1.到官网下载软件并安装2.安装插件3.场景中添加检测管理器4.场景中添加手部模型 更多细节 导入步骤 1.到官网下载软件并安装 地址 重启电脑后连接设备 可以看到连接成功 2.安装插件 &#xff08;也可以看官方教程&#xff09; Project—>PackageManag…
阅读更多...
从AI应用排行榜选择AI产品（9月）

从AI应用排行榜选择AI产品（9月）

2024年9月13日&#xff0c;OpenAI公司宣布推出其全新的AI模型&#xff1a;o1&#xff0c;在数学、编程和科学问题的解决处理能力上取得了显著进步。该模型通过自我对弈强化学习&#xff08;Self-play RL&#xff09;和思维链&#xff08;Chain of Thought, CoT&#xff09;技术…
阅读更多...
openssl的使用

openssl的使用

1、编译 Github下载&#xff1a;https://github.com/openssl/openssl 官网下载&#xff1a;https://openssl-library.org/source/index.html 官网历史版本&#xff1a;https://www.openssl.org/source/old/ 1.1 Windows下编译 我的文章&#xff1a;OPC UA使用 Openssl库编译…
阅读更多...
0基础带你入门Linux之使用

0基础带你入门Linux之使用

1.Ubuntu软件管理 回顾一下&#xff0c;我们之前使用su root切换到root模式&#xff0c;使用who 发现为什么显示的还是bd用户呢&#xff1f;为什么呢&#xff1f; 这个who是主要来查看的是我们登录的时候是以什么用户登录的 所以即使我们使用who进行查看的时候显示的还是bd用…
阅读更多...
【浅水模型MATLAB】尝试复刻SCI论文中的溃坝流算例

【浅水模型MATLAB】尝试复刻SCI论文中的溃坝流算例

【浅水模型MATLAB】尝试复刻SCI论文中的溃坝流算例 前言问题描述控制方程及数值方法浅水方程及其数值计算方法边界条件的实现 代码框架与关键代码模拟结果 更新于2024年9月17日 前言 这篇博客算是学习浅水方程&#xff0c;并利用MATLAB复刻Liang (2004)1中溃坝流算例的一个记录…
阅读更多...
SysML图例-重症输液泵

SysML图例-重症输液泵

SysML图中词汇 infusion pump 输液泵。替代传统的重力式吊瓶输液&#xff0c;达到更加精准和更加安全给药的目的。 syringe pump 注射泵。也称作微量输液泵&#xff0c;主要目的是对容量式输液泵在微量给药方面的一个补充。
阅读更多...
ECMAScript与JavaScript的区别

ECMAScript与JavaScript的区别

目录 一、什么是ECMAScript&#xff1f; 二、什么是JavaScript&#xff1f; 三、ECMAScript与JavaScript的关系 3.1 ECMAScript规范版本 3.2 JavaScript的实现 四、ECMAScript与JavaScript的主要区别 4.1 规范与实现的区别 4.2 版本更新 4.3 环境支持 4.4 语言特性 五…
阅读更多...
中秋期间互联网产品故障事件（晋江、115盘、阿里云盘）盘点

中秋期间互联网产品故障事件（晋江、115盘、阿里云盘）盘点

24年中秋期间&#xff0c;除了肆掠的“贝碧嘉”台风外&#xff0c;互联网故障bug事件也不少&#xff0c;趁着有空盘点下&#xff0c;可作为员工信息安全培训案例。 一&#xff1a;晋江文学城访问异常&#xff08;基础环境故障类&#xff09; 9月14日&#xff0c;“晋江崩了”冲…
阅读更多...
【python设计模式3】创建型模式2

【python设计模式3】创建型模式2

目录 抽象工厂模式 建造者模式 单例模式 创建型模式概述 抽象工厂模式 抽象工厂模式&#xff1a;定义一个工厂类的接口让工厂子类来创建一系列相关或者相互依赖的对象。相比工厂方法模式&#xff0c;抽象工厂模式中的每一个具体工厂都生产一套产品。下面是生产厂商生产一部手…
阅读更多...
VSCode扩展连接虚拟机MySQL数据库

VSCode扩展连接虚拟机MySQL数据库

在虚拟机安装MySQL vscode通过ssh远程登录Ubuntu 在vscode终端运行以下命令。 sudo apt-get install mysql-server-5.7 用以下命令确认MySQL是否安装完成。 sudo mysql MySQL安装成功。 在VSCode安装SQL扩展 扩展名&#xff1a;MySQL Shell for VS Code。 安装完成后&am…
阅读更多...
【2025】智慧居家养老服务平台的设计与实现、基于AI的居家养老服务平台、居家养老服务平台开发、智慧养老服务平台设计

【2025】智慧居家养老服务平台的设计与实现、基于AI的居家养老服务平台、居家养老服务平台开发、智慧养老服务平台设计

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…
阅读更多...
55.【C语言】字符函数和字符串函数(strstr函数)

55.【C语言】字符函数和字符串函数(strstr函数)

11.strstr函数 *简单使用 strstr: string string cplusplus的介绍 点我跳转 翻译: 函数 strstr const char * strstr ( const char * str1, const char * str2 ); 或另一个版本char * strstr ( char * str1, const char * str2 ); 寻找子字符串 返回指向第一次出现在字…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023