floodfill算法（二）

embedded/2024/11/11 23:09:49/

目录

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

1. 题目链接：417. 太平洋大西洋水流问题

2. 题目描述：

3. 解法

🌴算法思路：

🌴算法代码：

二、扫雷游戏

1. 题目链接：529. 扫雷游戏

2. 题目描述：

3. 解法

🌴算法思路：

🌴算法代码：

三、衣橱整理

1. 题目链接：LCR 130. 衣橱整理

2. 题目描述：

3. 解法

🌴算法思路：

🌴算法流程：

🌴算法代码：

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

1. 题目链接：417. 太平洋大西洋水流问题

2. 题目描述：

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：

输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示：

  • m == heights.length
  • n == heights[r].length
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 105

3. 解法

🌴算法思路：

正难则反。

        如果直接去判断某⼀个位置是否既能到大西洋也能到太平洋，会重复遍历很多路径。

        我们反着来，从大西洋沿岸开始反向 dfs ，这样就能找出那些点可以流向大西洋；同理，从太平洋沿岸也反向 dfs ，这样就能找出那些点可以流向太平洋。那么，被标记两次的点，就是我们要找的结果。

🌴算法代码：

class Solution 
{int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};public: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));// 1.处理 pac 洋for (int j = 0; j < n; j++) dfs(heights, 0, j, pac);for (int i = 0; i < m; i++) dfs(heights, i, 0, pac);// 2.处理 atl 洋for (int i = 0; i < m; i++) dfs(heights, i, n - 1, atl);for (int j = 0; j < n; j++) dfs(heights, m - 1, j, atl);vector<vector<int>> ret;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (pac[i][j] && atl[i][j])ret.push_back({i, j});return ret;}void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& vis){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] && heights[i][j] <= heights[x][y]){dfs(heights, x, y, vis);}}}
};

二、扫雷游戏

1. 题目链接：​​​​​​​529. 扫雷游戏

2. 题目描述：

让我们一起来玩扫雷游戏！

给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：

  • 'M' 代表一个 未挖出的 地雷，
  • 'E' 代表一个 未挖出的 空方块，
  • 'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
  • 数字（'1' 到 '8'）表示有多少地雷与这块 已挖出的 方块相邻，
  • 'X' 则表示一个 已挖出的 地雷。

给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（'M' 或者 'E'）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

根据以下规则，返回相应位置被点击后对应的盘面：

  1. 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X' 。
  2. 如果一个 没有相邻地雷 的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
  3. 如果一个 至少与一个地雷相邻 的空方块（'E'）被挖出，修改它为数字（'1' 到 '8' ），表示相邻地雷的数量。
  4. 如果在此次点击中，若无更多方块可被揭露，则返回盘面。

示例 1：

输入：board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
输出：[["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

示例 2：

输入：board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
输出：[["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 50
  • board[i][j] 为 'M'、'E'、'B' 或数字 '1' 到 '8' 中的一个
  • click.length == 2
  • 0 <= clickr < m
  • 0 <= clickc < n
  • board[clickr][clickc] 为 'M' 或 'E'

3. 解法

🌴算法思路：

模拟类型的 dfs 题目。

首先要搞懂题目要求，也就是游戏规则。

从题目所给的点击位置开始，根据游戏规则，来⼀次 dfs 即可。

🌴算法代码：

class Solution 
{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) {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 (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);}}}}
};

三、衣橱整理

1. 题目链接：​​​​​​​LCR 130. 衣橱整理

2. 题目描述：

家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

示例 1：

输入：m = 4, n = 7, cnt = 5
输出：18

提示：

  • 1 <= n, m <= 100
  • 0 <= cnt <= 20

3. 解法

🌴算法思路：

        这是⼀道非常典型的「搜索」类问题。

        我们可以通过「深搜」或者「宽搜」，从 [0, 0] 点出发，按照题目的「规则」一直往 [m - 1, n - 1] 位置走。

        同时，设置⼀个全局变量。每次走到⼀个合法位置，就将全局变量加⼀。当我们把所有能走到的路都走完之后，全局变量里面存的就是最终答案。

🌴算法流程：

递归函数设计：

a. 参数：当前所在的位置 [i, j] ，行走的边界 [m, n] ，坐标数位之和的边界 k ；

b. 递归出口：

  1. [i, j] 的坐标不合法，也就是已经超出能走的范围；
  2. [i, j] 位置已经走过了（因此我们需要创建⼀个全局变量 bool st[101][101] ，来标记当前位置是否走过）；
  3. [i, j] 坐标的数位之和大于 k ；上述情况的任何⼀种都是递归出口。

c. 函数体内部：

  1. 如果这个坐标是合法的，就将全局变量 ret++ ；
  2. 然后标记⼀下 [i, j] 位置已经遍历过；
  3. 然后去 [i, j] 位置的上下左右四个方向去看看。

辅助函数：

  1. 检测坐标 [i, j] 是否合法；
  2. 计算出 i，j 的数位之和，然后与 k 作比较即可。

主函数：

  • 调用递归函数，从 [0 ,0] 点出发。

辅助的全局变量：

  1. 二维数组 bool st[101][101] ：标记 [i, j] 位置是否已经遍历过；
  2. 变量 ret ：记录一共到达多少个合法的位置。
  3. 上下左右的四个坐标变换。

🌴算法代码：

class Solution 
{int m, n, cnt;bool vis[101][101];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int ret;
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;}
};

http://www.ppmy.cn/embedded/113515.html

相关文章

C++复习day12

C++复习day12

IO流 一、C语言的输入和输出 C语言中我们用到的最频繁的输入输出方式就是scanf ()与printf()。 scanf(): 从标准输入设备(键 盘)读取数据&#xff0c;并将值存放在变量中。printf(): 将指定的文字/字符串输出到标准输出设备(屏幕)。 注意宽度输出和精度输出控制。C语言借助了…
阅读更多...
Mysql 的查询过慢如何排查以及优化

Mysql 的查询过慢如何排查以及优化

1.慢查询: (1).查看慢查询的日志文件有没有打开&#xff1a;show variables like ‘slow_query_log’; (2).因为默认是没有开启的所以一般我们需要手动的去开启&#xff1a;set global slow_query_logon; (3).查看慢查询的时间&#xff1a;show variables like ‘…
阅读更多...
语音识别（Speech Recongnition）

语音识别（Speech Recongnition）

Speech Recongnition TTS&#xff08;Text-to-Speech&#xff09;&#xff0c;属于Speech Synthesis 典型模型Tacotron&#xff0c;用的是一个典型的 Seq2Seq Attention 的模型架构。它输出还会有个后处理&#xff08;Post-processing&#xff09;才会产生声音频谱&#xff08…
阅读更多...
如何删除git提交记录

如何删除git提交记录

今天在提交github时&#xff0c;不小心提交了敏感信息&#xff0c; 不要问我提交了啥&#xff0c;问就是不知道 查了下资料&#xff0c;终于找到简单粗暴的方式来删除提交记录。方法如下 git reset --soft HEAD~i i代表要恢复到多少次提交前的状态&#xff0c;如指定i 2&…
阅读更多...
Oracle数据库中的Oracle Real Application Clusters是什么

Oracle数据库中的Oracle Real Application Clusters是什么

Oracle Real Application Clusters&#xff08;简称Oracle RAC&#xff09;是Oracle数据库的一个关键特性&#xff0c;它允许多个数据库实例同时访问和管理同一个数据库。这种架构设计的目的是为了提高数据库系统的可扩展性、可用性和性能。 Oracle RAC的核心特点包括&#xf…
阅读更多...
局域网windows下使用Git

局域网windows下使用Git

windows下如何使用局域网进行git部署 准备工作第一步 &#xff0c;ip设置设置远程电脑的ip设置&#xff0c;如果不会设置请点击[这里](https://blog.csdn.net/Black_Friend/article/details/142170705?spm1001.2014.3001.5501)设置本地电脑的ip&#xff1a;验证 第二步&#x…
阅读更多...
从数据仓库到数据中台再到数据飞轮：社交媒体的数据技术进化史

从数据仓库到数据中台再到数据飞轮：社交媒体的数据技术进化史

前言 大家好&#xff0c;我是在大数据方面具有一定理解的博主。今天我想分享下从数据仓库到数据中台再到数据飞轮:社交媒体的数据技术进化史&#xff0c;也是这篇文章主题。我亲眼目睹了社交媒体的快速发展&#xff0c;以及随之而来的海量数据的生成与积累。如何有效地管理和利…
阅读更多...
高级c语言（五）

高级c语言（五）

输出缓冲区&#xff1a; 当我们使用标准库的输出系列函数打印数据到屏幕&#xff0c;数据并不会立即显示到屏幕上&#xff0c;而先存储到一块内存中&#xff0c;我们把这块内存称为输出缓冲区&#xff0c;等满足相关条件后&#xff0c;再从缓冲区中显示到屏幕&#xff0c;相关…
阅读更多...
最新文章

Copyright @ 2022~2023