如何建立网站建设,网络推广公司运作,wordpress 爱在发烧,wordpress 修改域名文章目录 1. 什么是FloodFill问题2. 用什么方法解决FloodFill问题3. 具体例题773.图像渲染200.岛屿数量695.岛屿的最大面积130.被围绕的区域 1. 什么是FloodFill问题
一般floodfill问题可以描述为#xff1a;给定一个二维矩阵#xff0c;其中每个元素代表一个像素点#xf… 文章目录 1. 什么是FloodFill问题2. 用什么方法解决FloodFill问题3. 具体例题773.图像渲染200.岛屿数量695.岛屿的最大面积130.被围绕的区域 1. 什么是FloodFill问题
一般floodfill问题可以描述为给定一个二维矩阵其中每个元素代表一个像素点并给定一个起始点、目标颜色和填充颜色。问题要求将以起始点为中心与其相邻且具有相同颜色的所有区域都填充为目标颜色。 2. 用什么方法解决FloodFill问题
我们通常使用下面两种方法解决FloodFill算法问题
DFS深搜 算法通常使用递归实现在处理当前像素点的相邻像素点时递归调用 DFS 函数不断深入直到无法找到相邻像素为止。
BFS 宽搜算法通常使用队列实现将起始像素点加入队列中并不断扩展队列中的像素点直到队列为空为止。
下面直接结合例题来理解两种解题方法。 3. 具体例题
第一道题 “图像渲染” 是下面例题中作为基座的一道题讲解会尽量详细后面的题
773.图像渲染 题意分析
即对于一个矩阵我们随机选取一个元素将该元素与对于其有相同值的上下左右 的元素对上下左右的元素继续找上下左右 均上色为color。本质上就是找区域内的相邻元素。
解法
DFS深度优先搜索
“搜索一个位置的上下左右坐标并对其上下左右坐标继续搜索上下左右坐标” 的过程可以理解为将一个主问题分解为多个子问题的过程适用递归解决。
我们知道深度优先搜索即一条路走到死而该递归过程也是深搜的思想。 思路
先记录题目给我们的当前位置的颜色prevColor如果当前位置color则直接返回以当前位置开始直接进行递归操作 对于递归函数先将当前位置上色随后遍历上下左右四个方向的元素每遍历到一个元素对该元素进行进行dfs操作即可完成对 相连像素点的上色
代码
class Solution {
private:int dx[4] {0, 0, -1, 1}; // 用于计算上下左右位置的下标int dy[4] {-1, 1, 0, 0};int m, n, _color, prevColor; // 定义成全局变量方便调用也可以传参// dfs: 查看 坐标(x, y) 上下左右四个元素并更改颜色void dfs(vectorvectorint image, int x, int y) {image[x][y] _color; // 当前位置上色for(int k 0; k 4; k) {int nx x dx[k]; // 计算一个方向的坐标int ny y dy[k];// 确保不越界 以及 值相同if(nx 0 nx m ny 0 ny n image[nx][ny] prevColor)dfs(image, nx, ny); // 递归找连结的需要上色的像素}}public:vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {prevColor image[sr][sc]; // 记录最开始 / 当前元素颜色if(prevColor color) return image; // 如果当前像素已经是所需颜色则直接返回矩阵m image.size(), n image[0].size();_color color;dfs(image, sr, sc);return image;}
};BFS宽度优先搜索
宽度优先搜索利用队列和循环每次将坐标入队随后将其上下左右四个坐标入队通过每次取队列元素持续该过程直到队列为空
思路
先记录当前位置的颜色prevColor如果当前位置color则直接返回将当前位置坐标入队每次提取当前元素的坐标并将其上色将上下左右四个方向的元素符合条件的入队重复此过程
代码
class Solution {
public:typedef pairint, int pii;int dx[4] {0, 0, -1, 1}; // 查询当前像素的上下左右时xy坐标的更改int dy[4] {-1, 1, 0, 0};vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {// 边界情况int tmp image[sr][sc]; // 记录要更改的像素值if(tmp color) return image;queuepii 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];int y b dy[i];// 如果未越界则入队if(x 0 x image.size() y 0 y image[0].size() image[x][y] tmp)q.push({x, y});}}return image;}
};200.岛屿数量 题意分析
矩阵由’1’, ‘0’ 两个元素组成每一块相连的1横着竖着相连组成的区域为一个岛屿我们需要找到矩阵中岛屿的数量。
解法
DFS深度优先搜索
思路
首先我们定义visit数组用于记录矩阵中每一位元素是否已经被遍历过如果为true则不去执行该位的操作。遍历整个矩阵对于矩阵的每个符合要求的元素都执行dfs算法每次循环中dfs彻底结束则统计出了一片岛屿ret最终结果关于此题的dfs 用于将矩阵中坐标为x, y的元素及其上下左右的元素标记
代码
class Solution {
private:int ret 0; // 定义为全局变量方便dfs改动和调用int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};int m, n;vectorvectorbool visit; // 存储网格是否被检索过的信息private:// 通过递归将当前位置的岛屿统计出来// dfs 将grid[x][y] 位置所在的岛屿统计出来void dfs(vectorvectorchar grid, int x, int y) {// 将当前位置检索设置为truevisit[x][y] true;for(int i 0; i 4; i){int nx x dx[i];int ny y dy[i];if((nx 0 nx m) (ny 0 ny n) !visit[nx][ny] grid[nx][ny] 1){dfs(grid, nx, ny);}}}public:int numIslands(vectorvectorchar grid) {m grid.size(), n grid[0].size();visit.resize(m, vectorbool(n, false)); // 初始化visit数组for(int i 0; i m; i){for(int j 0; j n; j){if(!visit[i][j] grid[i][j] 1) // 该位置并未检索过且值为1{ret;dfs(grid, i, j);}}}return ret;}
};BFS宽度优先搜索
思路
这里宽搜和深搜的代码非常相似只需要将bfs代码内部将递归改为使用队列即可具体代码中注解不再多余解释
代码
class Solution {
public:int ret 0;int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};int m, n;vectorvectorbool visit; // 存储网格是否被检索过的信息void bfs(vectorvectorchar grid, int x, int y) {queuepairint, int q; // 存储位置坐标q.push({x, y});while(!q.empty()){auto [a, b] q.front(); // 取出队头元素q.pop();for(int k 0; k 4; k) // 遍历该位置的上下左右四个位置{int nx a dx[k];int ny b dy[k];if((nx 0 nx m) (ny 0 ny n) !visit[nx][ny] grid[nx][ny] 1){q.push({nx, ny});visit[nx][ny] true;}}}}int numIslands(vectorvectorchar grid) {m grid.size(), n grid[0].size();visit.resize(m, vectorbool(n, false));// 遍历矩阵for(int i 0; i m; i){for(int j 0; j n; j){if(!visit[i][j] grid[i][j] 1){ret;bfs(grid, i, j);}}}return ret;}
};695.岛屿的最大面积 题意分析
该题和上一题岛屿数量在解法和思路上可以说非常相似只是前者要求岛屿数量而后者要求岛屿最大面积我们只需定义一个变量每次统计一个岛屿后比较并更新该变量即可。
解法
DFS深度优先搜索
思路
重复该题和上一题岛屿数量在解法和思路上可以说非常相似只是前者要求岛屿数量而后者要求岛屿最大面积我们只需定义一个变量每次统计一个岛屿后比较并更新该变量即可。
所以重点在于ret何时统计
对于深搜我们每次执行当前递归函数彻底结束后执行ret max(count, ret);即更新最大面积。因为递归函数结束后此时count记录的就是新岛屿的面积则在dfs后更新最大面积。
代码
class Solution {
private:vectorvectorbool visit;int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};int ret 0, count 0; // 统计岛屿面积int m, n;public:void dfs(vectorvectorint grid, int x, int y) {visit[x][y] true; // 将当前位置检索设置为truefor(int k 0; k 4; k){int nx x dx[k];int ny y dy[k];if((nx 0 nx m) (ny 0 ny n) !visit[nx][ny] grid[nx][ny] 1) // 判断是否合法{count;dfs(grid, nx, ny);}} }int maxAreaOfIsland(vectorvectorint grid) {m grid.size(), n grid[0].size();visit.resize(m, vectorbool(n, false));for(int i 0; i m; i){for(int j 0; j n; j){count 1; // 当前位置开始从1开始if(!visit[i][j] grid[i][j] 1){dfs(grid, i, j);ret max(count, ret); // 找到最大面积}}}return ret;}
};BFS宽度优先搜索
思路
ret何时统计
对于宽搜我们每次执行一次bfs函数后进行ret max(ret, count),因为执行dfs后count的值就是新岛屿的面积所以我们在其后判断更新最大面积。
代码
class Solution {
private:typedef pairint, int pii;vectorvectorbool visit;int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};int ret 0, count 0; // 统计岛屿面积int m, n;public:void bfs(vectorvectorint grid, int x, int y) {visit[x][y] true; // 将当前位置检索设置为truequeuepii q; // 队列存储坐标q.push({x, y}); // 将起始坐标添加到队列中while(!q.empty()) // 广度优先搜索{auto [x, y] q.front();q.pop();for(int k 0; k 4; k){int nx x dx[k];int ny y dy[k];if((nx 0 nx m) (ny 0 ny n) !visit[nx][ny] grid[nx][ny] 1) // 判断是否合法{count;visit[nx][ny] true;q.push({nx, ny}); // 将新的岛屿坐标添加到队列中}}} }int maxAreaOfIsland(vectorvectorint grid) {m grid.size(), n grid[0].size();visit.resize(m, vectorbool(n, false));for(int i 0; i m; i){for(int j 0; j n; j){count 1; // 当前位置开始从1开始if(!visit[i][j] grid[i][j] 1){bfs(grid, i, j);ret max(ret, count);}} }return ret;}
};130.被围绕的区域 题意分析
题目要求我们找到所有被’X’围绕的’O’并将其改为’X’ 被’X’围绕的’O’ 正难则反我们直接找到被’X’围绕的’O’是有难度的则可以逆转思维 找到所有不被’X’包围的’O’将这些’O’改为’T’改成任意字符随后遍历矩阵将所有’O’改为’X’此时即完成了题目要求最后将’T’再改回X即可 解法
DFS深度优先搜索
思路
根据题意分析的思路讲解首先遍历矩阵四边对边缘元素执行dfs函数 dfs: 用于将当前位置联结的’O’改为’T’ 当 循环dfs 全部执行完毕此时四边相连的’O’已经被改为’T’遍历矩阵将剩余的’O’改为’X’将’T’改为’O’。
代码
class Solution {
public:int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};int m, n;// dfs将当前位置周围的O改为Tvoid dfs(vectorvectorchar board, int x, int y) {board[x][y] T;for(int k 0; k 4; k){int a x dx[k];int b y dy[k];if((a 0 a m) (b 0 b n) board[a][b] O) // 保证合法性{dfs(board, a, b);}}}void solve(vectorvectorchar board) {m board.size(), n board[0].size();// 正难则反将未被X围绕的O更改然后遍历矩阵找O// 1. 矩阵四边周围的O 改为 Tfor(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 / 将T改为Ofor(int i 0; i m; i){for(int j 0; j n; j){if(board[i][j] O) board[i][j] X;if(board[i][j] T) board[i][j] O;}}}
};BFS宽度优先搜索
思路
和前面的题一致我们用队列进行宽搜的实现
首先创建visit数组用于记录矩阵中的每位是否被遍历过除了bfs函数思路不同其余与dfs完全一致这里主要在于bfs的写法 先将当前位置入队并在visit中改为true只要队列不为空持续获取上下左右方向的元素符合要求的入队更改为true持续此过程。
代码
class Solution {
public:int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};vectorvectorbool visit;int m, n;// bfs将当前位置周围的O改为Tvoid bfs(vectorvectorchar board, int x, int y) {queuepairint, int q;visit[x][y] true;board[x][y] T;q.push({x, y}); // 将起始位置入队while(!q.empty()){auto [x, y] q.front();q.pop();for(int k 0; k 4; k){int nx x dx[k];int ny y dy[k];if((nx 0 nx m) (ny 0 ny n) !visit[nx][ny] board[nx][ny] O){board[nx][ny] T; // 将O改为Tvisit[nx][ny] true; // 修改为单等号q.push({nx, ny});}}}}void solve(vectorvectorchar board) {m board.size(), n board[0].size();visit.resize(m, vectorbool(n, false)); // bfs算法中记录该位置是否被检查过// 正难则反将未被X围绕的O更改然后遍历矩阵找O// 1. 矩阵四边周围的O 改为 Tfor(int i 0; i m; i) // 上下边{if(board[i][0] O) bfs(board, i, 0);if(board[i][n - 1] O) bfs(board, i, n - 1);}for(int j 0; j n; j) // 左右边{if(board[0][j] O) bfs(board, 0, j);if(board[m - 1][j] O) bfs(board, m - 1, j);}// 2. 还原将O改为X / 将T改为Ofor(int i 0; i m; i){for(int j 0; j n; j){if(board[i][j] O) board[i][j] X;if(board[i][j] T) board[i][j] O;}}}
};
