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.lengthn == heights[r].length1 <= m, n <= 2000 <= 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是列下标）。根据以下规则，返回相应位置被点击后对应的盘面：
- 如果一个地雷（
'M'）被挖出，游戏就结束了- 把它改为'X'。- 如果一个 没有相邻地雷 的空方块（
'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。- 如果一个 至少与一个地雷相邻 的空方块（
'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。- 如果在此次点击中，若无更多方块可被揭露，则返回盘面。
示例 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.lengthn == board[i].length1 <= m, n <= 50board[i][j]为'M'、'E'、'B'或数字'1'到'8'中的一个click.length == 20 <= clickr < m0 <= clickc < nboard[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 <= 1000 <= cnt <= 20
3. 解法
🌴算法思路：
这是⼀道非常典型的「搜索」类问题。
我们可以通过「深搜」或者「宽搜」，从 [0, 0] 点出发，按照题目的「规则」一直往 [m - 1, n - 1] 位置走。
同时，设置⼀个全局变量。每次走到⼀个合法位置，就将全局变量加⼀。当我们把所有能走到的路都走完之后，全局变量里面存的就是最终答案。
🌴算法流程：
递归函数设计：
a. 参数：当前所在的位置 [i, j] ，行走的边界 [m, n] ，坐标数位之和的边界 k ；
b. 递归出口：
- [i, j] 的坐标不合法，也就是已经超出能走的范围；
- [i, j] 位置已经走过了（因此我们需要创建⼀个全局变量 bool st[101][101] ，来标记当前位置是否走过）；
- [i, j] 坐标的数位之和大于 k ；上述情况的任何⼀种都是递归出口。
c. 函数体内部：
- 如果这个坐标是合法的，就将全局变量 ret++ ；
- 然后标记⼀下 [i, j] 位置已经遍历过；
- 然后去 [i, j] 位置的上下左右四个方向去看看。
辅助函数：
- 检测坐标 [i, j] 是否合法；
- 计算出 i，j 的数位之和，然后与 k 作比较即可。
主函数：
- 调用递归函数，从 [0 ,0] 点出发。
辅助的全局变量：
- 二维数组 bool st[101][101] ：标记 [i, j] 位置是否已经遍历过；
- 变量 ret ：记录一共到达多少个合法的位置。
- 上下左右的四个坐标变换。
🌴算法代码：
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;}
};