最新有限公司网站,实时热点新闻事件2023,网络运维管理软件,宁波人才网什么是FloodFill算法
中文#xff1a;洪水灌溉。假设这一块4*4的方格是一块土地#xff0c;有凸起的地方#xff0c;也有凹陷的地方#xff08;凹陷的地方用负数表示#xff09;。此时下大雨发洪水#xff0c;会把凹陷的地方填满。绿色圈起来的属于一块区域#xff08;…
什么是FloodFill算法
中文洪水灌溉。假设这一块4*4的方格是一块土地有凸起的地方也有凹陷的地方凹陷的地方用负数表示。此时下大雨发洪水会把凹陷的地方填满。绿色圈起来的属于一块区域上下左右四个方向有时候题目也会问八个方向包括斜着相连的题目会问有多少块区域被填满或者问被填满的最大区域是哪个或某一块区域的边长是多少。但是本质都是让我们在一块区域找性质相同的连通块。
DFS——深度优先遍历递归从某一点开始一条路走到黑。以最右列的为例从-1出发向下--2--10--12此时发现-12的上下左右都走不了在拐回去到-10然后发现-10左边可以走--4--3。
BFS——宽度优先遍历一层一层拨开。还是以最右边为例从-1开始拓展一层上下左右发现能把-2扩展出来接着继续扩展一层上下左右-3和-10扩展出来接着在扩展一层上下左右把-4和-12扩展出来。 图像渲染
图像渲染 题目解析
给一个起始位置让我们把与起始位置相连上下左右四个方向且数字相同的区域全都修改为newcolor 算法原理
BFS刚开始给定一个位置一层一层扫描上下左右方向扩展值相同就添加进来
第一层扩进来 接着以新扩进来的为起点开始上下左右扩展蓝色为第二、三层扩展 黄色为第四层扩展 然后在扩展的过程中一边扩展一边把值修改为2.为了方便访问上下左右四个方向的数组可以定义一个dx、dyx、y的变化量。原坐标分别去相加就能遍历到四个方向的坐标位置 代码实现
class Solution
{typedef pairint, int PII;int dx[4] {0, 0, 1, -1}; //定义一个变化量dx、dyxy分别去加就能遍历到上下左右四个方向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();queuePII q;q.push({sr, sc});while(!q.empty()){auto [a, b] q.front();image[a][b] color;q.pop();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;}
};岛屿数量
岛屿数量 题目解析
给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
算法原理
解法BFS从左往右扫描当第一次遇到1陆地时就把这块陆地连接的岛屿找到使用BFS宽搜一遍找到一个岛屿ret
这里有一个细节问题如果第一个1宽搜完之后到下一个1蓝色的如果再上下左右宽搜的话就会重复统计了为此我们有两种办法1.直接修改原数组为0但这个方法一般会直接修改接口我们再笔试刷题时一般都是接口类型的函数2.创建一个与原数组同等规模的数组vis[m][n]用来标记已经被BFS过的区域如果宽搜过记为true没被宽搜过记为false。此时对下个1进行上下左右宽搜时如果该区域已经被标记为true就不管即可。每次标记为true时再让ret
代码实现
class Solution
{int dx[4] {1, -1, 0, 0};int dy[4] {0, 0, 1, -1};bool vis[301][301];int m, n;
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 !vis[i][j]){ret;bfs(grid, i, j); // 把这块陆地全部标记⼀下}}}return ret;}void bfs(vectorvectorchar grid, int i, int j){queuepairint, int q;q.push({i, j});vis[i][j] true;while(q.size()){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 !vis[x][y]){q.push({x, y});vis[x][y] true;}}}}};岛屿的最大面积
岛屿的最大面积 题目解析 算法原理
要找到所有连通块中的最大面积就要先找能统计出一个连通块的面积。先从左到右从上往下扫描矩阵当遇到一个没有遍历过的1的时候相当于此时找到一个陆地。我们依旧定义一个bool类型的vis数组用来标记当前位置是否遍历过。然后我们在BFS过程中不仅要标记还要搞一个count计算面积。当层序遍历结束后我们就把count返回给主函数。
代码实现
class Solution
{int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};bool vis[51][51];int m, n;
public:int maxAreaOfIsland(vectorvectorint 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 !vis[i][j]){ret max(ret, bfs(grid, i, j));}}}return ret;}int bfs(vectorvectorint grid, int i, int j){int count 0;queuepairint, int q;q.push({i, j});vis[i][j] true;count;while(q.size()){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 !vis[x][y]){ q.push({x, y});vis[x][y] true;count;}}}return count;}
};被围绕的区域
被围绕的区域 题目解析
找到被X包围的O
算法原理
扫描区域当扫描到一个O时就把与O相连的O一起修改为X。当扫描的边界的O时要多加一个判断因为他的下方没有X此时不属于被包围故不能修改。
解法一直接做先BFS一遍判断区域是否合法然后再来一遍开始修改我们之前的FloodFill算法是一边修改一边遍历当到刚刚所说的边界情况时想再修改回X发现此时周围已经全部变成X了就无法判断了。
也可能有同学会想到先遍历一遍如果发现是好的区域非边界情况修改当是边界情况就不修改此时需要遍历两次
解法二正难则反本题难处理的地方是边界情况的判断。那么我们就可以反过来先处理边界情况的连通块先对四条边进行一次遍历先把边上的连通块都找到将其修改为无关的字符。接下来只需要遍历此时不需要再BFS或DFS矩阵将矩阵中剩下的的O修改为X最后再把 . 修改为O即可。因为把边界情况处理过后此时剩下的O一定都是被包围的。
代码实现
class Solution
{int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m, n;
public:void solve(vectorvectorchar board) {m board.size(), n board[0].size();// 1. 先处理边界上的 O 联通块全部修改成 .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);}for(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);}// 2. 还原for(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;}void bfs(vectorvectorchar board, int i, int j){queuepairint, int q;q.push({i, j});board[i][j] .;while(q.size()){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){q.push({x, y});board[x][y] .;}}}}
};
