公司招聘网站,响应式网站 app,别人用我公司营业执照备案做网站,建模教程绝境之中才窥见#xff0c;Winner#xff0c;Winner FloodFill算法简介: floodfill又翻译成漫水填充。我们可以将下面的矩阵理解为一片具有一定高度的坡地#xff0c;此时突发洪水#xff0c;洪水会将高度0的地方填满。 话句话来说#xff0c;Fl…
绝境之中才窥见WinnerWinner FloodFill算法简介: floodfill又翻译成漫水填充。我们可以将下面的矩阵理解为一片具有一定高度的坡地此时突发洪水洪水会将高度0的地方填满。 话句话来说FloodFill算法是为了找出那些具有相同性质的区域。那我们现在就来看看一些经典的使用floodfill算法的题目。 图像渲染
(1) 题目解析 这类题目的代码部分都是将模拟的过程转化成代码。
(2) 算法代码
dfs:
class Solution {
public:int m,n;int prev;int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {m image.size(),n image[0].size();if(image[sr][sc] color) return image;prev image[sr][sc];dfs(image,sr,sc,color);return image;}void dfs(vectorvectorint image, int i,int j,int newcolor){// 从这一点出发每一个方向去 递归相邻节点image[i][j] newcolor;for(int k0;k4;k){int xidx[k],y jdy[k];// 满足 要渲染更改的值 if(x0 xm y0 yn image[x][y] prev){dfs(image,x,y,newcolor);}}}
}; bfs:
class Solution {
public:typedef pairint,int PII;int m,n;int prev;int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {m image.size(),n image[0].size();if(image[sr][sc] color) return image;// 当前位置会被修改为newcolor 这里是保存需要被渲染的值prev image[sr][sc];bfs(image,sr,sc,color);return image;}void bfs(vectorvectorint image, int i,int j,int newcolor){queuePII que;image[i][j] newcolor;que.push({i,j});while(que.size()){// 取出已经被渲染的位置并将它的相邻位置满足条件的 插入进队列auto [a,b] que.front();que.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0 xm y0 yn image[x][y] prev){image[x][y] newcolor;que.push({x,y});}}}}
}; 岛屿数量
(1) 题目解析 注: 进行bfs或dfs时需要注意防止统计已经遍历过的位置。我们有两种解决方法其一就是对原数组内部的值进行修改区别于目标条件其二就是创建一个新的布尔数组标记每一个遍历过的点。 (2) 算法代码
dfs:
class Solution {
public:int m,n;bool vis[301][301];int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};int numIslands(vectorvectorchar grid) {m grid.size(),n grid[0].size();int count 0;for(int i0;im;i)for(int j0;jn;j){// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过if(grid[i][j] 1 !vis[i][j]) {count;vis[i][j] true; // 标记dfs(grid,i,j);}}return count;}void dfs(vectorvectorchar grid,int i,int j){// 这里的dfs 只需将与(i,j) 相连的岛屿统计即可for(int k0;k4;k){int xidx[k],yjdy[k];if(x0 xm y0 yn grid[x][y] 1 !vis[x][y]){vis[x][y] true;dfs(grid,x,y);}}}
};
bfs: class Solution {public:int m,n;bool vis[301][301];int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};int numIslands(vectorvectorchar grid) {m grid.size(),n grid[0].size();int count 0;for(int i0;im;i)for(int j0;jn;j){// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过if(grid[i][j] 1 !vis[i][j]) {count;vis[i][j] true; // 标记bfs(grid,i,j);}}return count;}void bfs(vectorvectorchar grid,int i,int j){// 这里的bfs 只需将与(i,j) 相连的岛屿统计即可// bfs通常需要借助队列来实现queuepairint,int que;que.push({i,j});while(que.size()){auto [a,b] que.front();que.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0 xm y0 yn grid[x][y] 1 !vis[x][y]){vis[x][y] true;que.push({x,y});}}}}}; 岛屿的最大面积
(1) 题目解析 这道题和上个题目十分类似只不过这道题目的结果是求这些岛屿的最大面积所以我们需要对相连岛屿数量进行统计并最终返回一个最大值。
(2) 算法代码
dfs:
class Solution {
public:int m,n;bool vis[301][301];int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};int ret,count;int maxAreaOfIsland(vectorvectorint grid) {m grid.size(),n grid[0].size(),ret 0;for(int i0;im;i)for(int j0;jn;j){// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过if(grid[i][j] 1 !vis[i][j]) {count 0;dfs(grid,i,j);ret max(ret,count);}}return ret;}void dfs(vectorvectorint grid,int i,int j){vis[i][j] true;count;for(int k0;k4;k){int xidx[k],yjdy[k];if(x0 xm y0 yn grid[x][y] 1 !vis[x][y]){ dfs(grid,x,y);}}}
}; bfs:
class Solution {
public:int m,n;bool vis[301][301];int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};int ret,count;int maxAreaOfIsland(vectorvectorint grid) {m grid.size(),n grid[0].size(),ret 0;for(int i0;im;i)for(int j0;jn;j){// 遍历到岛屿进行一次dfs 并且这个位置没有被访问过if(grid[i][j] 1 !vis[i][j]) {count 0;vis[i][j] true; // 标记bfs(grid,i,j);ret max(ret,count);}}return ret;}void bfs(vectorvectorint grid,int i,int j){// 这里的bfs 只需将与(i,j) 相连的岛屿统计即可// bfs通常需要借助队列来实现queuepairint,int que;que.push({i,j});count;while(que.size()){auto [a,b] que.front();que.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0 xm y0 yn grid[x][y] 1 !vis[x][y]){count;vis[x][y] true;que.push({x,y});}}}}
}; 被围绕的区域
(1) 题目解析 但其实我们发现这两个dfs本质是做同样的事情但却因为判断边界我们需要写两份不同的dfs这是蛮麻烦的事情。我们换个思路直接用一个dfs将边界的O进行过滤并填上不相关的字符再将整个数组遍历遇到‘O’改为‘X’遇到这个不相关的字符改为O。
(2) 算法代码
dfs:
class Solution {
public:int m,n;bool vis[201][201];int dx[4] {0,0,-1,1};int dy[4] {1,-1,0,0};void solve(vectorvectorchar board) {m board.size(),n board[0].size();// 处理第一行和最后一行for(int j0;jn;j){if(board[0][j] O) dfs(board,0,j);if(board[m-1][j] O) dfs(board,m-1,j);}// 第一列 最后一列for(int i0;im;i){if(board[i][0] O) dfs(board,i,0);if(board[i][n-1] O) dfs(board,i,n-1);}for(int i0;im;i)for(int j0;jn;j){if(board[i][j] .) board[i][j] O;else if(board[i][j] O) board[i][j] X;}}void dfs(vectorvectorchar board,int i,int j){board[i][j] .;for(int k0;k4;k){int xidx[k],yjdy[k];if(x0 xm y0 yn board[x][y] O){dfs(board,x,y);}}}
}; bfs:
class Solution {
public:int m,n;bool vis[201][201];int dx[4] {0,0,-1,1};int dy[4] {1,-1,0,0};void solve(vectorvectorchar board) {m board.size(),n board[0].size();// 处理第一行和最后一行for(int j0;jn;j){if(board[0][j] O) bfs(board,0,j);if(board[m-1][j] O) bfs(board,m-1,j);}// 第一列 最后一列for(int i0;im;i){if(board[i][0] O) bfs(board,i,0);if(board[i][n-1] O) bfs(board,i,n-1);}for(int i0;im;i)for(int j0;jn;j){if(board[i][j] .) board[i][j] O;else if(board[i][j] O) board[i][j] X;}}void bfs(vectorvectorchar board,int i,int j){board[i][j] .;queuepairint,int que;que.push({i,j});while(que.size()){auto [a,b] que.front();que.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0 xm y0 yn board[x][y] O){board[x][y] .;que.push({x,y});}}}}
}; 扫雷
(1) 题目解析 经典的扫雷游戏至于玩法也就不过多解释。该题目考察的地方就在于点击一个点之后从这个 点开始进行对相邻领域的展开我们可以采用dfs或bfs完成。 当挖出的位置是一个雷将这个位置标记成‘X’游戏结束。当挖出的一个地方是空位置你需要首先去相邻区域查找是否有雷如果没有发现雷则标记为B否则就需要将搜查到的雷的个数标记在该位置处。 (2) 算法代码
dfs:
class Solution {
public:int m,n;bool vis[51][51];// 扫雷位置有八个位置需要被展开int dx[8] {0,0,-1,1,-1,1,-1,1};int dy[8] {1,-1,0,0,1,-1,-1,1};vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {m board.size(),n board[0].size();int i click[0],j click[1];if(board[i][j] M)board[i][j] X;elsedfs(board,i,j);return board;}void dfs(vectorvectorchar board,int i,int j){int count 0;// 统计雷的数量for(int k0;k8;k){int xidx[k],yjdy[k];if(x0 xm y0 yn board[x][y] M) count;}if(count){board[i][j] count 0;}else{board[i][j] B;for(int k0;k8;k){int xidx[k],yjdy[k];if(x0 xm y0 yn board[x][y] E) dfs(board,x,y);}}}
};
bfs:
class Solution {
public:int m,n;bool vis[51][51];// 扫雷位置有八个位置需要被展开int dx[8] {0,0,-1,1,-1,1,-1,1};int dy[8] {1,-1,0,0,1,-1,-1,1};vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {m board.size(),n board[0].size();int i click[0],j click[1];if(board[i][j] M)board[i][j] X;elsebfs(board,i,j);return board;}void bfs(vectorvectorchar board,int i,int j){queuepairint,int que;que.push({i,j});vis[i][j] true;while(que.size()){auto [a,b] que.front();que.pop();int count 0;// 统计雷的数量for(int k0;k8;k){int xadx[k],ybdy[k];if(x0 xm y0 yn board[x][y] M) count;}if(count){board[a][b] count 0;}else{board[a][b] B;for(int k0;k8;k){int xadx[k],ybdy[k];if(x0 xm y0 yn board[x][y] E){// 这里改为B 避免被其他点统计到 队列中去// 也可以使用 vis[x][y] ture; 进行标记 不被统计 board[x][y] B; que.push({x,y});}}}}}
}; 本篇到此结束感谢你的阅读。
祝你好运向阳而生~
