山西建设工程协会网站,长沙网站排名优化,我用织梦5.7做个网站应该把淘宝客店铺链接放到哪,现在哪个网站做网站好算法沉淀——BFS 解决 FloodFill 算法 01.图像渲染02.岛屿数量03.岛屿的最大面积04.被围绕的区域 BFS#xff08;广度优先搜索#xff09;解决 Flood Fill 算法的基本思想是通过从起始点开始#xff0c;逐层向外扩展#xff0c;访问所有与起始点相连且具有相同特性#xf… 算法沉淀——BFS 解决 FloodFill 算法 01.图像渲染02.岛屿数量03.岛屿的最大面积04.被围绕的区域 BFS广度优先搜索解决 Flood Fill 算法的基本思想是通过从起始点开始逐层向外扩展访问所有与起始点相连且具有相同特性颜色等的区域。在 Flood Fill 中通常是通过修改图像的像素颜色。 下面是 BFS 解决 Flood Fill 算法的步骤
初始化 将起始点的颜色修改为新的颜色将起始点加入队列。BFS 遍历 使用队列进行 BFS 遍历。每次从队列中取出一个位置检查其相邻的位置是否符合条件与起始点颜色相同如果符合则修改颜色并将其加入队列。这样不断扩展遍历。遍历直到完成 重复上述步骤直到队列为空即没有可继续扩展的位置为止。此时所有与起始点相连的区域都被成功修改。
在 Flood Fill 中BFS 保证了相邻区域的逐层遍历确保了所有相连的、颜色相同的区域都被填充为新的颜色。
01.图像渲染
题目链接https://leetcode.cn/problems/flood-fill/
有一幅以 m x n 的二维整数数组表示的图画 image 其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 从初始像素开始记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点……重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
示例 1:
输入: image [[1,1,1],[1,1,0],[1,0,1]]sr 1, sc 1, newColor 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间(坐标(sr,sc)(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意右下角的像素没有更改为2因为它不是在上下左右四个方向上与初始点相连的像素点。示例 2:
输入: image [[0,0,0],[0,0,0]], sr 0, sc 0, newColor 2
输出: [[2,2,2],[2,2,2]]思路
这个题我们可以使用最朴素的bfs遍历来解决。
代码
class Solution {const int dx[4] {0, 0, 1, -1}; // 表示上、下、左、右四个方向的相对坐标变化const int dy[4] {-1, 1, 0, 0};
public:vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {int prev image[sr][sc]; // 记录起始位置的颜色if (prev color) return image; // 如果新旧颜色相同不需要进行填充int m image.size(), n image[0].size();queuepairint, int q;q.push({sr, sc});while (!q.empty()) {auto [a, b] q.front();q.pop();image[a][b] color; // 修改当前位置的颜色for (int i 0; i 4; i) {int x a dx[i], y b dy[i];// 判断新的坐标是否越界并且颜色与旧颜色相同if (x 0 x m y 0 y n image[x][y] prev) {q.push({x, y});}}}return image;}
};初始化 记录起始位置的颜色 prev如果起始颜色和目标颜色相同直接返回原图。BFS 遍历 使用队列 q 进行 BFS 遍历。从起始位置开始逐层遍历相邻位置将颜色修改为目标颜色。遍历直到完成 重复上述步骤直到队列为空即没有可继续扩展的位置为止。此时所有与起始点相连的区域都被成功修改为新的颜色。
02.岛屿数量
题目链接https://leetcode.cn/problems/number-of-islands/
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
示例 1
输入grid [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]
]
输出1示例 2
输入grid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]
]
输出3提示
m grid.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 0 或 1
思路
使用bfs思想遍历每一个方格将一块遍历过的岛屿全都标记为海洋也就是0或者使用同等大小的数组进行遍历的标记。
代码
class Solution {const int dx[4] {0, 0, 1, -1}; // 表示上、下、左、右四个方向的相对坐标变化const int dy[4] {1, -1, 0, 0};int m, n; // m表示行数n表示列数queuepairint, int q; // 用于BFS的队列// BFS函数从起点 (i, j) 开始遍历并标记属于同一岛屿的所有位置void bfs(vectorvectorchar grid, int i, int j) {q.push({i, j}); // 将起点入队grid[i][j] 0; // 标记已经遍历过的位置while (!q.empty()) {auto [a, b] q.front();q.pop();for (int k 0; k 4; k) {int x a dx[k], y b dy[k];// 判断新的坐标是否越界并且是岛屿的一部分if (x 0 x m y 0 y n grid[x][y] 1) {q.push({x, y}); // 将相邻的岛屿位置入队grid[x][y] 0; // 标记已经遍历过的位置}}}}public:int numIslands(vectorvectorchar grid) {m grid.size(); // 获取行数n grid[0].size(); // 获取列数int ret 0; // 记录岛屿数量// 遍历整个网格for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {ret; // 发现新的岛屿增加计数bfs(grid, i, j); // 使用BFS遍历并标记所有属于同一岛屿的位置}}}return ret; // 返回岛屿数量}
};初始化 定义了方向数组 dx 和 dy表示上、下、左、右四个方向的相对坐标变化。初始化队列 q用于BFS遍历。BFS遍历 对于每个未被访问的岛屿起点调用 bfs 函数进行BFS遍历。在BFS过程中将属于同一岛屿的位置标记为已访问。遍历整个网格 使用两层循环遍历整个网格如果发现未访问过的岛屿起点就调用 bfs 函数进行遍历并增加岛屿数量计数。返回结果 最终返回岛屿的数量。
03.岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0代表水包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿则返回面积为 0 。
示例 1
输入grid [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出6
解释答案不应该是 11 因为岛屿只能包含水平或垂直这四个方向上的 1 。示例 2
输入grid [[0,0,0,0,0,0,0,0]]
输出0 提示
m grid.lengthn grid[i].length1 m, n 50grid[i][j] 为 0 或 1
思路
总体和上面的题目解法一样只不过我们在遍历每个岛屿时顺便计算个数即岛屿的面积每次计算完再比较最后返回最大的岛屿面积。
代码
class Solution {const int dx[4] {0, 0, 1, -1}; // 上、下、右、左四个方向的相对坐标变化const int dy[4] {-1, 1, 0, 0};queuepairint, int q; // 用于BFS的队列int m, n; // m 表示行数n 表示列数// BFS 函数从起点 (i, j) 开始遍历并标记属于同一岛屿的所有位置int bfs(vectorvectorint grid, int i, int j) {int count 1; // 记录岛屿的大小q.push({i, j}); // 将起点入队grid[i][j] 0; // 标记已经遍历过的位置while (!q.empty()) {auto [a, b] q.front();q.pop();for (int k 0; k 4; k) {int x a dx[k], y b dy[k];// 判断新的坐标是否越界并且是岛屿的一部分if (x 0 x m y 0 y n grid[x][y] 1) {grid[x][y] 0; // 标记已经遍历过的位置count; // 增加岛屿的大小q.push({x, y}); // 将相邻的岛屿位置入队}}}return count;}public:int maxAreaOfIsland(vectorvectorint grid) {int ret 0; // 记录最大岛屿面积m grid.size(); // 获取行数n grid[0].size(); // 获取列数// 遍历整个网格for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {ret max(ret, bfs(grid, i, j)); // 计算并更新最大岛屿面积}}}return ret; // 返回最大岛屿面积}
};初始化 定义了方向数组 dx 和 dy表示上、下、左、右四个方向的相对坐标变化。初始化队列 q用于BFS遍历。BFS遍历 对于每个未被访问的岛屿起点调用 bfs 函数进行BFS遍历。在BFS过程中将属于同一岛屿的位置标记为已访问并统计岛屿的大小。遍历整个网格 使用两层循环遍历整个网格如果发现未访问过的岛屿起点就调用 bfs 函数进行遍历并计算并更新最大岛屿面积。返回结果 最终返回最大岛屿面积。
04.被围绕的区域
题目链接https://leetcode.cn/problems/surrounded-regions/
给你一个 m x n 的矩阵 board 由若干字符 X 和 O 找到所有被 X 围绕的区域并将这些区域里所有的 O 用 X 填充。
示例 1
输入board [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]
输出[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]
解释被围绕的区间不会存在于边界上换句话说任何边界上的 O 都不会被填充为 X。 任何不在边界上或不与边界上的 O 相连的 O 最终都会被填充为 X。如果两个元素在水平或垂直方向相邻则称它们是“相连”的。示例 2
输入board [[X]]
输出[[X]]提示
m board.lengthn board[i].length1 m, n 200board[i][j] 为 X 或 O
思路
这里我们可以使用bfs先处理所有与边界有关的位置把它修改成其他字符再依次遍历留在格子中的字母O就是需要被修改的而改成其他字符的就可以改回字母O。
代码
class Solution {const int dx[4] {0, 0, 1, -1}; // 上、下、右、左四个方向的相对坐标变化const int dy[4] {-1, 1, 0, 0};int m, n; // m 表示行数n 表示列数queuepairint, int q; // 用于BFS的队列// BFS 函数从起点 (i, j) 开始遍历并标记属于同一区域的所有位置void bfs(vectorvectorchar board, int i, int j) {q.push({i, j}); // 将起点入队board[i][j] #; // 标记已经遍历过的位置while (!q.empty()) {auto [a, b] q.front();q.pop();for (int k 0; k 4; k) {int x a dx[k], y b dy[k];// 判断新的坐标是否越界并且是未被围绕的区域if (x 0 x m y 0 y n board[x][y] O) {board[x][y] #; // 标记已经遍历过的位置q.push({x, y}); // 将相邻的未被围绕的区域位置入队}}}}public:void solve(vectorvectorchar board) {m board.size(); // 获取行数n board[0].size(); // 获取列数// 对边界上的O进行BFS遍历标记为#for (int i 0; i n; i) {if (board[0][i] O) bfs(board, 0, i);if (board[m - 1][i] O) bfs(board, m - 1, i);}for (int i 1; i m - 1; i) {if (board[i][0] O) bfs(board, i, 0);if (board[i][n - 1] O) bfs(board, i, n - 1);}// 遍历整个网格将未被标记的O修改为X已经标记的#修改回Ofor (int i 0; i m; i) {for (int j 0; j n; j) {if (board[i][j] #) board[i][j] O;else if (board[i][j] O) board[i][j] X;}}}
};
