洪水灌溉算法 + 总结

floodfill算法

1. 寻找相同性质的联通块，可以使用dfs或者bfs解决，比如把1连通块的周围都修改为2

图像渲染

题目链接

题解

1.我们通过将以sr，sc为起始点，将该点周围的联通块都修改为color
2. 全局变量： p记录要修改的联通块的值，m，n矩阵的长和宽，坐标dx，dy向上下左右方向搜索
3. 细节处理：如果起始点（sr，sc）就是color的值，不需要修改直接返回矩阵，因为该点周围已经被渲斓为color颜色了，这样会无限渲斓下去，因为是同一个值，未改变，具体可以看实例二

代码

class Solution 
{
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};void dfs(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，建议使用第一种，第二中如果想要恢复成原来的数组比较困难

代码

class Solution 
{
public:int m,n;int count;// 记录联通块的个数int numIslands(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};void dfs(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，找下最大值

代码

class Solution 
{
public:int m,n;int ret;// 记录最大岛屿面积int count;bool vis[51][51];int maxAreaOfIsland(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};void dfs(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，这就是正难则反

代码

class Solution 
{
public:int m,n;void solve(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'else if(board[i][j] == 'O') board[i][j] = 'X';}}}int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};void dfs(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. 正难则反，可以从小的格子向大的格子走，如果比此格子小则停止，这样不会重复走，从太平洋那边走的使用一个标记数组，从大西洋那边走的，使用一个标记数组，如果两个标记数组都为真则这些格子是可以流向两个洋的

代码

class Solution 
{
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一定要传引用为了修改原始数组中的值void dfs(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（递归式地展开，可能没有地雷就连续地展开）

代码

class Solution 
{
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;}void dfs(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的点，算出这些点的个数

代码

class Solution 
{
public:int m,n;int count;bool vis[101][101];int wardrobeFinishing(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};void dfs(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个方向上去搜索