图像渲染
题目来源：733.图像渲染
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
算法原理：
本题要用BFS来解决此问题：
具体如下：
- 从给定位置开始，上下左右搜索为第一层。
- 从第一层两个位起点继续上下左右一层一层剥开。
- 依次内推…
- 当某一层上下左右搜索中，没有发现目标值就结束。
在上面搜索过程中，我们可以边在搜索过程中就进行修改，达到优化效果。
代码实现：
在代码实现之前，我们先做一下预处理。
通常BFS宽度优先遍历中，要对四个方向或者八个方向进行搜索，此时我们可以定义一个向量数组。
dx与dy为横坐标与纵坐标的偏移量。我们让坐标加上这个偏移量就是搜索后的宽度优先遍历的四个方向。
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; queue<PII> q; q.push({sr,sc}); //获取起始点位置 int m=image.size(),n=image[0].size(); while(q.size()) { auto [a,b]=q.front(); q.pop(); image[a][b]=color; 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&&y<n&&image[x][y]==prev) { //满足情况入队 q.push({x,y}); } } } return image; } };
岛屿数量
题目来源：岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
算法原理：
题目很好理解：
看到此类问题，首选BFS。
我们来模拟一下这个过程：
扫描矩阵，找到一个陆地的时候，就将这个陆地连接的联通快找到。怎么找用BFS。
此时找到一个岛屿，定义一个变量，让我们的ret++即可，但是有个问题：在我们层序遍历扩展到一个位置时，是不能让他拓展回去的。
那么此时有两种办法：
- 在原数组进行修改
- 定义一个bool数组
第一种会修改原始数组的值，我们不推荐。
通常我们会采取第二种方式：
定义一个vis[m][n]数组：
只要我们遍历过次位置，就将定义为true.数组还有个作用，当我们发现值为1，为true时ret不用++反之false就++。
代码实现：
class Solution { //向量数组 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; 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]==false) { 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&&y<n&&grid[x][y]=='1'&&vis[x][y]==false) { //满足情况入队 q.push({x,y}); vis[x][y]=true; } } } } };
