【算法】【floodfill】洪水灌溉

本文主要是介绍【算法】【floodfill】洪水灌溉，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 岛屿数量

👉🔗题目链接

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

几个注意点：

1. 二维深搜，巧妙使用全局方向矩阵
2. 状态表记录，可以不改动原表
3. 在搜索时注意 边界值 + 条件！！！

class Solution {
public:vector<vector<bool>> vis;int m, n;int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();vis = vector<vector<bool>>(m, vector<bool>(n));int count = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1' && !vis[i][j]){count++;dfs(grid, i, j);}}}return count;}int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};void dfs(const vector<vector<char>>& grid, int i, int j){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 && grid[x][y] == '1' && !vis[x][y]){dfs(grid, x, y);}}}
};

---

2. 岛屿最大面积

👉🔗题目链接

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

和上述代码雷同！仔细设计一下哪些做全局变量吧~

---

3. 被围绕的区域

👉🔗题目链接

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充

和上述的题目相似，但有差别！
在边界上出现的 ‘O’ 不能计入，如果还使用之前的方法，在触碰边界条件的时候回退，代码逻辑编写起来是有困难的！怎么办呢?

正着写麻烦，就反着来吧。

先解决所有边界上的值，周围一圈的值，碰到一个 ‘O’ 就深搜一下，修改成 ‘+’。再把里面的都修改成 ‘X’ 不就解决啦！

class Solution {
public:int m, n;void solve(vector<vector<char>>& board) {m = board.size();n = board[0].size();// 1.将外面一圈的O相连的连通块,都处理了for(int i = 0; i < m; i++){if(board[i][0] == 'O') dfs(board, i, 0);if(board[i][n-1] == 'O') dfs(board, i, n-1);}for(int j = 0; j < n; j++){if(board[0][j] == 'O') dfs(board, 0, j);if(board[m-1][j] == 'O') dfs(board, m-1, j);}// 2.还原：将O都改成X，将+都改成Ofor(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';}   }int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};// 把与进入位置相连的块都改成+void dfs(vector<vector<char>>& board, int i, int j){board[i][j] = '+';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 && board[x][y] == 'O')dfs(board, x, y);}}
};

---

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

👉🔗题目链接

手动翻译一下脑残的题目：给出的矩阵中，每个数字是高于海平面的高度。水可以从高处往低处流，也可以往相同高度流，矩阵边界的水都可以往海里流。按照他给出的两个海的位置，返回一系列[x, y]位置，要求这些位置上的水，既可以流向大西洋也可以流向太平洋。(图中橙色标记的格子的 index 就是满足条件的，也就是需要返回的)

解法1：

• 暴力解法，对每一个格子进行判断，既能到左上，又能到右下则加入返回集合。
• 逻辑比较好写，就是有很多重复路径，不太聪明（sos

解法2：

• 正难则反
• 从边界开始反推，哪些地方的水是可以流向太平洋 / 大西洋的！
• 最后两边一汇总就是最后可以输出的结果。

class Solution {
public:int m, n;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>> ath(m, vector<bool>(n));vector<vector<int>> ret;// 1.填充两张状态表for(int i = 0; i < m; i++){// 太平洋:左if(!pac[i][0]) dfs(heights, i, 0, pac);// 大西洋:右if(!ath[i][n-1]) dfs(heights, i, n-1, ath);}for(int j = 0; j < n; j++){// 太平洋: 上if(!pac[0][j]) dfs(heights, 0, j, pac);// 大西洋: 下if(!ath[m-1][j]) dfs(heights, m-1, j, ath);}// 2.找出重合坐标for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(pac[i][j] && ath[i][j])ret.push_back(vector<int>{i,j});return ret;}int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};void dfs(const vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& status){status[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 && heights[x][y] >= heights[i][j] && !status[x][y])dfs(heights, x, y, status);}}
};

---

5. 扫雷游戏

👉🔗题目链接

• ‘M’ 代表一个 未挖出的 地雷，
• ‘E’ 代表一个 未挖出的 空方块，
• ‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块， 数字（‘1’ 到 ‘8’）表示有多少地雷与这块已挖出的 方块相邻， ‘X’ 则表示一个 已挖出的 地雷。 给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（‘M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

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

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

👉🔗游戏链接

class Solution {
public:int m, n;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) {m = board.size();n = board[0].size();int i = click[0];int j = click[1];// 是地雷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] = '0' + count;return;}// 没有地雷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);}}
};

能少走两次 count_and_modify_M 的写法：

class Solution {
public:int m, n;int dx[8] = {0,0,1,-1,1,1,-1,-1};int dy[8] = {1,-1,0,0,1,-1,1,-1};// 求 i,j 位置一周地雷的个数，如果有地雷，则修改boardint count_and_modify_M (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 > 0)board[i][j] = '0' + count;return count;}vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {m = board.size();n = board[0].size();int i = click[0];int j = click[1];// 是地雷if(board[i][j] == 'M') {board[i][j] = 'X';return board;}// 是已经挖开的if(board[i][j] == 'B' || (board[i][j] >= '0'+ 1 && board[i][j] <= '0'+ 8))return board;// 是挨着地雷的if(count_and_modify_M(board, i, j) != 0)return board;// 进入递归并判断dfs(board, i, j);return board;}void dfs(vector<vector<char>>& board, int i, int j){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' || board[x][y] == 'M') && count_and_modify_M(board, x, y) == 0)dfs(board, x, y);}}
};

---

6. 机器人的运动范围

👉🔗题目链接

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

拿到题目，别被数位之和唬住了。

机器人能走的路径是连续的，这里也就是从(0,0)开始，一次深搜的事儿，数位之和只是一个边界条件嘛！

#include <vector>
#include <iostream>
using namespace std;
class Solution 
{
public:int m, n, k, ret = 0;vector<vector<bool>> vis;int movingCount(int threshold, int rows, int cols) {m = rows, n = cols, k = threshold;vis = vector<vector<bool>>(m, vector<bool>(n));dfs(0, 0);return ret;   }int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};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] && is_accessible(x, y))dfs(x, y);}}bool is_accessible(int x, int y){int sum = 0;while(x){sum += x % 10;x /= 10;}while(y){sum += y % 10;y /= 10;}if(sum <= k)return true;return false;}
};

---

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(✿◡‿◡) 若有差错恳请留言指正~~

---

这篇关于【算法】【floodfill】洪水灌溉的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---