【ps】本篇有 7 道 leetcode OJ。
目录
一、算法简介
二、相关例题
1）图像渲染
.1- 题目解析
.2- 代码编写
2）岛屿数量
.1- 题目解析
.2- 代码编写
3）岛屿的最大面积
.1- 题目解析
.2- 代码编写
4）被围绕的区域
.1- 题目解析
.2- 代码编写
5）太平洋大西洋水流问题
.1- 题目解析
.2- 代码编写
6）扫雷游戏
.1- 题目解析
.2- 代码编写
7）衣橱整理
.1- 题目解析
.2- 代码编写
一、算法简介
FloodeFill算法即填充算法，原理就是从一个点开始向四周扩散，向周围可以走到的点填充颜色，直到将可扩散到的点全部填充颜色。
通常使用下面两种方法解决FloodFill算法问题：
- BFS （宽搜）算法通常使用队列实现，将起始像素点加入队列中，并不断扩展队列中的像素点，直到队列为空为止。
- DFS（深搜） 算法通常使用递归实现，在处理当前像素点的相邻像素点时，递归调用 DFS 函数，不断深入直到无法找到相邻像素为止。
假设这一块4*4的方格是一块土地，有凸起的地方，也有凹陷的地方（凹陷的地方用负数表示）。此时下大雨发洪水，会把凹陷的地方填满。绿色圈起来的属于一块区域（上下左右四个方向，有时候题目也会问八个方向包括斜着相连的），题目会问有多少块区域被填满，或者问被填满的最大区域是哪个，或某一块区域的边长是多少。但是本质都是在一块区域找性质相同的连通块。
- DFS：深度优先遍历（递归）：从某一点开始一条路走到黑。以最右列的为例，从-1出发，向下->-2->-10->-12，此时发现-12的上下左右都走不了，在拐回去到-10，然后发现-10左边可以走->-4->-3。
- BFS：宽度优先遍历：一层一层拨开。还是以最右边为例，从-1开始拓展一层（上下左右）发现能把-2扩展出来，接着继续扩展一层上下左右，-3和-10扩展出来；接着在扩展一层上下左右，把-4和-12扩展出来。
int dx[4] = {0, 0 , -1, 1};
int dy[4] = {1, -1 , 0, 0};
// i点加dx，dy就是i点的上下左右的下标 二、相关例题
1）图像渲染
733. 图像渲染
.1- 题目解析
利用深搜 DFS，遍历到与该点相连的所有像素相同的点，然后将其修改成指定的像素即可。
.2- 代码编写
class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int m,n;int prev;//最初的着色
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {if(image[sr][sc]==color)return image;m=image.size(),n=image[0].size();prev=image[sr][sc];dfs(image,sr,sc,color);return image;}void dfs(vector<vector<int>>& image, int i, int j, int color){image[i][j]=color;for(int k=0;k<4;k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){dfs(image,x,y,color);}}}
};2）岛屿数量
200. 岛屿数量
.1- 题目解析
遍历整个矩阵，每次找到一块陆地，也就是找到了一个岛屿，并用一个变量 ret 来对岛屿数量计数。
特别的，遇到一块岛屿就将它全部变成海洋，这样的话，下次遍历到这块岛屿的时候，它已经是海洋了，不会影响最终结果，其中变成海洋的操作，可以利用 DFS 解决。
.2- 代码编写
class Solution {vector<vector<bool>> vis;//标识岛屿是否被遍历过（更改成海洋）int m, n;public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();vis = vector<vector<bool>>(m, vector<bool>(n));int ret = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (!vis[i][j] && grid[i][j] == '1') {ret++;vis[i][j] = true;dfs(grid, i, j);}}return ret;}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 = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&grid[x][y] == '1') {vis[x][y] = true;dfs(grid, x, y);}}}
};3）岛屿的最大面积
695. 岛屿的最大面积
.1- 题目解析
遍历整个矩阵，每当遇到一块土地的时候，就用 DFS 将与这块土地相连的整个岛屿的面积计算出来,然后在搜索得到的所有的岛屿面积求一个最大值即可。在搜索过程中，为了防止搜到重复的土地，可以开一个同等规模的 bool 数组，标记一下这个位置是否已经被访问过。
.2- 代码编写
class Solution {bool vis[51][51];int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};int m,n;int count;//记录岛屿面积
public:int maxAreaOfIsland(vector<vector<int>>& 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(!vis[i][j] && grid[i][j]==1){count=0;dfs(grid,i,j);ret=max(ret,count);}return ret;}void dfs(vector<vector<int>>& grid,int i,int j){count++;vis[i][j]=true;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0 && x<m && y>=0 && y<n&& !vis[x][y] && grid[x][y]==1){dfs(grid,x,y);}}}
};4）被围绕的区域
130. 被围绕的区域
.1- 题目解析
正难则反。
可以先利用 DFS 将与边缘相连的 'O' 区域修改成无关字符，然后重新遍历矩阵，将没有标记过的 'O' 全修改成 'X' 即可，再把无关字符全还原成'O'。
.2- 代码编写
class Solution {int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};int m,n;
public:void solve(vector<vector<char>>& board) {m=board.size(),n=board[0].size();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);}for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(board[i][j]=='.')board[i][j]='O';else if(board[i][j]=='O')board[i][j]='X';}}void dfs(vector<vector<char>>& board,int i,int j){board[i][j]='.';for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0 && x<m && y>=0 && y<n&& board[x][y]=='O'){dfs(board,x,y);}}}
};5）太平洋大西洋水流问题
417. 太平洋大西洋水流问题
.1- 题目解析
题目要求返回既可以流向太平洋、又可以流向大西洋的单元格坐标。
如果直接去判断某一个位置是否既能到大西洋也能到太平洋，会重复遍历很多路径。那么我们就可以正难则反，从大西洋沿岸开始反向 DFS，这样就能找出哪些点可以流向大西洋；同理，从太平洋沿岸也反向 DFS ，这样就能找出那些点可以流向太平洋，而被标记两次的点，就是要找的结果。
.2- 代码编写
class Solution {int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};int m,n;
public:vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {m=h.size(),n=h[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(h,0,j,pac);for(int i=0;i<m;i++)dfs(h,i,0,pac);//处理大西洋for(int i=0;i<m;i++)dfs(h,i,n-1,atl);for(int j=0;j<n;j++)dfs(h,m-1,j,atl);vector<vector<int>> ret;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;}void dfs(vector<vector<int>>& h,int i,int j,vector<vector<bool>>& vis){vis[i][j]=true;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0 && x<m && y>=0 && y<n&& !vis[x][y] && h[x][y]>=h[i][j]){dfs(h,x,y,vis);}}}
};6）扫雷游戏
529. 扫雷游戏
.1- 题目解析
从题目所给的点击位置开始，根据游戏规则，来一次 DFS 即可。DFS 的大致步骤，就是统计一下周围的地雷个数，有地雷就在当前位置放上周围地雷的个数，然后返回，没有地雷就改当前位置为没有地雷的空白块 B，然后 DFS 周围的未挖出的空方块 E。
.2- 代码编写
class Solution {int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};int dy[8] = {0, 0, 1, -1, -1, -1, 1, 1};int m, n;public: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 = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {count++;}}//周围有地雷，修改数字，然后游戏结束if (count) {board[i][j] = count + '0';return;//周围没有地雷只有空方格，继续dfs周围的方格} else {board[i][j] = 'B';for (int k = 0; k < 8; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {dfs(board,x,y);}}}}
};7）衣橱整理
LCR 130. 衣橱整理
.1- 题目解析
可以通过深搜或者宽搜，从 [0, 0] 点出发，按照题目的规则一直往 [m - 1, n - 1] 位置走。 同时设置一个全局变量。每次走到一个合法位置，就将全局变量加一。当我们把所有能走到的路都走完之后，全局变量里面存的就是最终答案。
.2- 代码编写
class Solution {int m,n,k;bool vis[101][101];int ret;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:int wardrobeFinishing(int _m, int _n, int cnt) {m=_m,n=_n,k=cnt;dfs(0,0);return ret;}void dfs(int i,int j){ret++;vis[i][j]=true;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0 && x<m && y>=0 && y<n&& !vis[x][y] && check(x,y)){dfs(x,y);}}}bool check(int i,int j){int tmp=0;while(i){tmp+=i%10;i/=10;}while(j){tmp+=j%10;j/=10;}return tmp<=k;}
};