floodfill算法（二）

目录

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

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;}
};