dfs 解决 部分矩阵洪流/floodfill算法题(水流问题、扫雷游戏、衣橱整理、C++)

本文主要是介绍dfs 解决 部分矩阵洪流/floodfill算法题(水流问题、扫雷游戏、衣橱整理、C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
    • 1. 什么是FloodFill问题
    • 2. 用什么方法解决FloodFill问题
  • 算法题
    • 417.太平洋大西洋水流问题
    • 529.扫雷游戏
    • LCR130.衣橱整理

前言

1. 什么是FloodFill问题

一般floodfill问题可以描述为:给定一个二维矩阵,其中每个元素代表一个像素点,并给定一个起始点、目标颜色和填充颜色。问题要求将以起始点为中心,与其相邻且具有相同颜色的所有区域都填充为目标颜色。

在这里插入图片描述


2. 用什么方法解决FloodFill问题

我们通常使用下面两种方法解决FloodFill算法问题:

DFS(深搜) 算法通常使用递归实现,在处理当前像素点的相邻像素点时,递归调用 DFS 函数,不断深入直到无法找到相邻像素为止。

BFS (宽搜)算法通常使用队列实现,将起始像素点加入队列中,并不断扩展队列中的像素点,直到队列为空为止。

在解决Floodfill问题时,暴力搜索(也称为递归法或深度优先搜索)是一种直接且简单的方法。具体步骤如下:

  1. 选择起始点: 从指定的起始单元格开始,通常这是填充区域的起点。

  2. 检查相邻单元格: 递归地检查当前单元格的所有相邻单元格(上、下、左、右)。如果相邻单元格与起始单元格的颜色相同,则继续填充。

  3. 填充颜色: 将当前单元格的颜色更改为目标颜色。

  4. 递归调用: 对所有相邻单元格递归执行步骤2和3。

  5. 停止条件: 如果单元格已被填充或不符合条件,则停止递归。


算法题

417.太平洋大西洋水流问题

在这里插入图片描述

思路

  1. 初始化

    • 定义矩阵的大小 mn
    • 使用两个布尔矩阵 pacatl,分别表示从太平洋和大西洋可以到达的格子。
  2. 深度优先搜索 (DFS)

    • 从太平洋边界(第一行和第一列)和大西洋边界(最后一行和最后一列)开始 DFS,标记每个可以到达的格子。
    • dfs 函数会向四个方向探索,只在相邻格子的高度不低于当前格子的情况下继续探索。
  3. 结果合并

    • 遍历整个矩阵,收集同时在 pacatl 中为 true 的格子,即能同时流向太平洋和大西洋的格子。

代码

class Solution {
public:int m, n;int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {m = heights.size();n = heights[0].size();vector<vector<bool>> pac(m, vector<bool>(n));vector<vector<bool>> atl(m, vector<bool>(n)); // 分别用于表示大西洋与太平洋的流向情况// 从外向内:// 太平洋 - 第一行与第一列的元素向内dfsfor(int j = 0; j < n; ++j) dfs(heights, 0, j, pac); // 第一行for(int i = 0; i < m; ++i) dfs(heights, i, 0, pac); // 第一列// 大西洋 - 最后一行与最后一列for(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); // 最后一列vector<vector<int>> ret;for(int i = 0; i < m; ++i) // 遍历数组,找对于某位置,表示两大洋的数组均为true的for(int j = 0; j < n; ++j){if(atl[i][j] && pac[i][j])ret.push_back({i, j});}return ret;}void dfs(vector<vector<int>>& heights, int x, int y, vector<vector<bool>>& visited){visited[x][y] = true;for(int k = 0; k < 4; ++k){int _x = x + dx[k], _y = y + dy[k];if(_x >= 0 && _y >= 0 && _x < m && _y < n && !visited[_x][_y] && heights[_x][_y] >= heights[x][y]){dfs(heights, _x, _y, visited);}}}
};

529.扫雷游戏

思路

  1. 初始化

    • mn 分别表示棋盘的行数和列数。
    • dxdy 数组用于表示八个方向的偏移量,以便遍历当前位置周围的方块。具体方向是:左、右、上、下、右下、右上、左下、左上。
  2. 更新棋盘 (updateBoard 函数):

    • 获取点击位置 ij
    • 如果点击的位置是地雷('M'),则将其标记为 'X',并返回更新后的棋盘。
    • 如果点击的位置不是地雷,调用 dfs 函数来递归揭示相关区域。
  3. 递归揭示 (dfs 函数):

    • 统计当前位置周围8个方向的地雷数量 count
    • 如果周围有地雷 (count > 0),将当前位置标记为对应的数字(地雷的数量),并返回。
    • 如果周围没有地雷 (count == 0),将当前位置标记为 'B',并继续递归处理周围未揭示的方块(即 'E')。

代码

class Solution {
public:int m, n;// 左上 上 右上 左 右 左下 下 右下// int dirs[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1};int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1};vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {int i = click[0], j = click[1];m = board.size(), n = board[0].size();if(board[i][j] == 'M'){board[i][j] = 'X';return board;}dfs(board, i, j);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(x >= 0 && x < m && y >= 0 && 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(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){dfs(board, x, y);}}}   }
};

LCR130.衣橱整理

在这里插入图片描述

思路

  1. 初始化

    • visited 是一个布尔矩阵,用于标记每个格子是否已经访问过。
    • dxdy 数组分别表示在网格中向右和向下移动的偏移量。
  2. wardrobeFinishing 函数

    • 这个函数初始化 visited 矩阵,并设置 _cnt_m_n,然后从 (0, 0) 位置开始调用 dfs 函数。
  3. dfs 函数

    • 递归遍历满足条件的格子。
    • 首先,访问当前位置 (i, j),并将 ret 计数器加 1。
    • 对于当前位置 (i, j),尝试向右 (i, j+1) 和向下 (i+1, j) 移动,检查这些新位置是否在网格内、是否未被访问,以及它们的行索引和列索引的数位和是否小于等于 cnt
    • 如果满足这些条件,递归调用 dfs 函数继续探索。
  4. digit 函数

    • 计算一个数字的数位和。例如,对于数字 23,它的数位和是 2 + 3 = 5

代码

class Solution {
public:// cnt = 2 即表格 行与列元素 数位之和 <= cnt 的个数// \ 0 1 2  (m = n = 3)// 0 0 1 2// 1 1 2 X// 2 2 X Xvector<vector<bool>> visited;int dx[2] = {1, 0};int dy[2] = {0, 1};int ret = 0, _cnt, _m, _n;int wardrobeFinishing(int m, int n, int cnt) {visited.resize(m, vector<bool>(n));_cnt = cnt, _m = m, _n = n;dfs(0, 0);return ret;}void dfs(int i, int j){++ret;visited[i][j] = true;for(int k = 0; k < 2; ++k){// 统计 满足条件的格子int x = dx[k] + i, y = dy[k] + j;if(x >= 0 && x < _m && y >= 0 && y < _n && digit(x) + digit(y) <= _cnt && !visited[x][y])dfs(x, y);}}// 求数位之和int digit(int num){int tmp = 0;while(num){tmp += num % 10;num /= 10;}return tmp;}
};

这篇关于dfs 解决 部分矩阵洪流/floodfill算法题(水流问题、扫雷游戏、衣橱整理、C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131950

相关文章

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python中ModuleNotFoundError: No module named ‘timm’的错误解决

《Python中ModuleNotFoundError:Nomodulenamed‘timm’的错误解决》本文主要介绍了Python中ModuleNotFoundError:Nomodulen... 目录一、引言二、错误原因分析三、解决办法1.安装timm模块2. 检查python环境3. 解决安装路径问题