【ps】本篇有 4 道 leetcode OJ。
目录
一、算法简介
二、相关例题
1）图像渲染
.1- 题目解析
.2- 代码编写
2）岛屿数量
.1- 题目解析
.2- 代码编写
3）岛屿的最大面积
.1- 题目解析
.2- 代码编写
4）被围绕的区域
.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- 题目解析
利用 BFS 遍历到与某点相连的所有像素相同的点，然后将其修改成指定的像素即可。
.2- 代码编写
class Solution {typedef pair<int, int> PII;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};public:vector<vector<int>> floodFill(vector<vector<int>>& 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();queue<PII> q;q.push({sr, sc});while (q.size()) {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;}
};2）岛屿数量
200. 岛屿数量
.1- 题目解析
被水（0）围起来的相连的陆地（1）才算一座岛屿。
我们可以遍历整个矩阵，每次找到一块陆地的时候，即找到了一个岛屿，就将其记入最终结果，同时将这个岛屿，全部变成海洋（由1改为0），这样的话，下次遍历到这个岛屿的时候，它已经是海洋了，不会影响最终结果。其中，变成海洋的操作，可以利用 BFS 解决。
但如果在面试中，面试官要求另外不能直接修改原始矩阵，那我们还可以用到一个全局的 bool 类型的矩阵，来记录陆地是否被遍历过。
.2- 代码编写
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(vector<vector<char>>& 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(vector<vector<char>>& grid, int i, int j) {queue<pair<int, 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;}}}}
};3）岛屿的最大面积
695. 岛屿的最大面积
.1- 题目解析
这道题是上一道题的变形。
我们只要在遍历矩阵寻找岛屿的时候，多一步来统计一下当前找出的岛屿面积即可。
.2- 代码编写
class Solution {int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;bool vis[51][51];
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(grid[i][j]==1 && !vis[i][j]){ret=max(bfs(grid,i,j),ret);}}}return ret;}int bfs(vector<vector<int>>& grid,int i,int j){int ret=0;//统计岛屿面积（1的个数）queue<pair<int,int>> q;q.push({i,j});vis[i][j]=true;ret++;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;ret++;}}}return ret;}
};4）被围绕的区域
130. 被围绕的区域
.1- 题目解析
不难想到，可以直接通过 bfs 将所有被 'X' 围起来的 'O' 修改为 'X'，但位于矩阵边缘的 'O' 其实是不必修改的，此时又该如何处理呢？
我们可以选择正难则反，先利用 bfs 将与边缘相连的 'O' 区域修改成无关字符，然后重新遍历矩阵，将没有标记过的 'O' 全修改成 'X' 即可，再把无关字符全还原成'O'。
.2- 代码编写
class Solution {int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;
public: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')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(vector<vector<char>>& board,int i,int j){queue<pair<int,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]='.';}}}}};
