洪水灌溉算法 + 总结
文章目录
floodfill算法
1. 寻找相同性质的联通块，可以使用dfs或者bfs解决，比如把1连通块的周围都修改为2
图像渲染
题解
1.我们通过将以sr，sc为起始点，将该点周围的联通块都修改为color
2. 全局变量： p记录要修改的联通块的值，m，n矩阵的长和宽，坐标dx，dy向上下左右方向搜索
3. 细节处理：如果起始点（sr，sc）就是color的值，不需要修改直接返回矩阵，因为该点周围已经被渲斓为color颜色了，这样会无限渲斓下去，因为是同一个值，未改变，具体可以看实例二
代码
classSolution{public:int m,n;int p;// 渲斓一个联通块 vector<vector<int>>floodFill(vector<vector<int>>& image,int sr,int sc,int color){ p = image[sr][sc]; m = image.size(),n = image[0].size();// 避免死循环,该点和该点周围一圈都是目标颜色,就无限进入循环中if(image[sr][sc]== color)return image;dfs(image,sr,sc,color);return image;}int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};voiddfs(vector<vector<int>>& image,int i,int j,int color){ image[i][j]= color;for(int k =0;k <4;k++){// 用例一:不会到达值是0的位置int x = dx[k]+ i,y = dy[k]+ j;if(x >=0&& x < m && y >=0&& y < n && image[x][y]== p){dfs(image,x,y,color);}}}};岛屿数量
题解
1. 计算联通块的数量，只要左右上下相邻的1就是一个连通块
2. 需要使用标记数组标记已经走过的1，避免重复到达同一个1，或者把搜索过的1都修改为0，建议使用第一种，第二中如果想要恢复成原来的数组比较困难
代码
classSolution{public:int m,n;int count;// 记录联通块的个数intnumIslands(vector<vector<char>>& grid){// 将遇到的一块陆地的联通块都变为海水,联通块加一,下次再遇到陆地依次类推 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'){dfs(grid,i,j); count++;}}}return count;}int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};voiddfs(vector<vector<char>>& grid,int i,int j){for(int k =0;k <4;k++){int x = dx[k]+ i,y = dy[k]+ j;if(x >=0&& x < m && y >=0&& y < n && grid[x][y]=='1'){ grid[x][y]='0';dfs(grid,x,y);}}}};岛屿的最大面积
题解
1. 使用标记数组标记已经使用过的格子，每次count设置为0，在dfs中每遇到一个是false并且值是1的格子就标记一下，并且count++，dfs返回之后更新下count，找下最大值
代码
classSolution{public:int m,n;int ret;// 记录最大岛屿面积int count;bool vis[51][51];intmaxAreaOfIsland(vector<vector<int>>& grid){ m = grid.size(),n = grid[0].size();for(int i =0;i < m;i++){for(int j =0;j < n;j++){if(!vis[i][j]&& grid[i][j]==1){ vis[i][j]=true; count =0;dfs(grid,i,j); ret =max(ret,count);}}}return ret;}int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};voiddfs(vector<vector<int>>& grid,int i,int j){ vis[i][j]=true; count++;for(int k =0;k <4;k++){int x = dx[k]+ i,y = dy[k]+ j;if(x >=0&& x < m && y >=0&& y < n &&!vis[x][y]&& grid[x][y]==1){// path在参数中回溯会自动恢复现场,path会比实际的值小dfs(grid,x,y);}}}};被围绕的区域
题解
1. 怎么检查四周是被X围绕的呢？
正难则反，正着的情况下，如果想要修改中间的O，需要一个dfs，如果想要四周的O不变，又需要一个dfs，如果想要将四周的O修改为X，又需要回溯去还原
2. 算法思路：
可以先使用dfs把四周的O修改为点，再在函数中将点的修改为O，O的修改为X，这就是正难则反
代码
classSolution{public:int m,n;voidsolve(vector<vector<char>>& board){ m = board.size(),n = board[0].size();// 1.把与边界'O'相连的连通块,修改为'.'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);}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);}// 2.把所有的'.'还原为'O',把'O'改为'X'for(int i =0;i < m;i++){for(int j =0;j < n;j++){if(board[i][j]=='.') board[i][j]='O';// 这里不可以写成if,因为可能是上面的'.'修改成的'O'elseif(board[i][j]=='O') board[i][j]='X';}}}int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};voiddfs(vector<vector<char>>& board,int i,int j){ board[i][j]='.';for(int k =0;k <4;k++){int x = dx[k]+ i,y = dy[k]+ j;if(x >=0&& x < m && y >=0&& y < n && board[x][y]=='O'){dfs(board,x,y);}}}};太平洋大西洋水流问题
题解
1. 正着来的话，每个格子可能会走多次，会超时，比如2可以向左走到太平洋中，5也可以向左走到太平洋中
2. 正难则反，可以从小的格子向大的格子走，如果比此格子小则停止，这样不会重复走，从太平洋那边走的使用一个标记数组，从大西洋那边走的，使用一个标记数组，如果两个标记数组都为真则这些格子是可以流向两个洋的
代码
classSolution{public:int m,n; vector<vector<int>>pacificAtlantic(vector<vector<int>>& heights){ vector<vector<int>> ret; m = heights.size(),n = heights[0].size(); vector<vector<bool>>pac(m,vector<bool>(n)); vector<vector<bool>>atl(m,vector<bool>(n));for(int j =0;j < n;j++){dfs(heights,0,j,pac);dfs(heights,m-1,j,atl);}for(int i =0;i < m;i++){dfs(heights,i,0,pac);dfs(heights,i,n-1,atl);}for(int i =0;i < m;i++){for(int j =0;j < n;j++){if(pac[i][j]&& atl[i][j]) ret.push_back({i,j});}}return ret;}int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};// oce一定要传引用为了修改原始数组中的值voiddfs(vector<vector<int>>& heights,int i,int j,vector<vector<bool>>& oce){ oce[i][j]=true;for(int k =0;k <4;k++){int x = dx[k]+ i,y = dy[k]+ j;if(x >=0&& x < m && y >=0&& y < n && heights[i][j]<= heights[x][y]&&!oce[x][y]){dfs(heights,x,y,oce);}}}};扫雷游戏
题解
1. 模拟 + dfs
2. 有一个非常重要的点是click下的点如果不是地雷的话，那么后面就不会再翻出地雷了
3. 算法思路：检测开始点击的点是否是地雷，如果是就把该点修改为’X’，如果不是就往下搜索，并且在dfs中新建一个变量统计地雷的个数，如果在该点的八个方向上有地雷，就在该点显示地雷的个数，并且返回（不会把地雷打开），如果没有地雷，把该点修改为’B’，并且在该点的八个方向上去dfs（递归式地展开，可能没有地雷就连续地展开）
代码
classSolution{public:int m,n;int dx[8]={-1,1,0,0,1,1,-1,-1};int dy[8]={0,0,-1,1,1,-1,1,-1}; vector<vector<char>>updateBoard(vector<vector<char>>& board, vector<int>& click){ m = board.size(),n = board[0].size();int x = click[0],y = click[1];// 点击的位置就是一个地雷if(board[x][y]=='M'){ board[x][y]='X';return board;}dfs(board,x,y);return board;}voiddfs(vector<vector<char>>& board,int i,int j){// 统计一下地雷的个数int count =0;// 寻找这一个点的这一圈的地雷个数for(int k =0;k <8;k++){int x = dx[k]+ i,y = dy[k]+ j;if(x >=0&& x < m && y >=0&& y < n && board[x][y]=='M'){ count++;}}// 如果周围存在地雷就标记一下if(count){ board[i][j]= count +'0';return;}else{// 如果周围不存在地雷 board[i][j]='B';for(int k =0;k <8;k++){int x = dx[k]+ i,y = dy[k]+ j;if(x >=0&& x < m && y >=0&& y < n && board[x][y]=='E'){dfs(board,x,y);}}}}};衣橱整理
题解
1. 细节处理：表示x的各数位之和，就是x的各个位置上的数字之和，开始的时候没有注意到
2. 这题就是向右或者向下去dfs，找到 两个坐标的数位之和 <= cnt的点，算出这些点的个数
代码
classSolution{public:int m,n;int count;bool vis[101][101];intwardrobeFinishing(int _m,int _n,int cnt){ m = _m,n = _n;dfs(0,0,cnt);if(0<= cnt) count++;return count;}int dx[2]={1,0};int dy[2]={0,1};voiddfs(int i,int j,int cnt){for(int k =0;k <2;k++){int x = dx[k]+ i,y = dy[k]+ j;int val1 = x,sum1 =0;int val2 = y,sum2 =0;while(val1){ sum1 +=(val1 %10); val1 /=10;}while(val2){ sum2 +=(val2 %10); val2 /=10;}if(x >=0&& x < m && y >=0&& y < n &&!vis[x][y]&& sum1 + sum2 <= cnt){ count++; vis[x][y]=true;dfs(x,y,cnt);}}}};总结
1. 学习到了正难则反的思想
2. 寻找性质相同的联通块，通过dfs将其修改或是统计联通块的个数
3. 无非都是通过4个方向或者是八个方向或者是2个方向上去搜索
