flood fill 算法常常用来找极大连通子图，这是必须掌握的基本算法之一！
图形渲染
算法原理
- 我们可以利用DFS遍历数组
- 把首个数组的值记为color，然后上下左右四个方向遍历二维数组数组
- 如果其他方块的值不等于color 或者越界就剪枝 return
代码实现
class Solution {
public:
int row,col;
int color;
bool visted[50][50];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void dfs(vector<vector<int>>& image, int sr, int sc, int new_color)
{
if( sr>= row || sr < 0 || sc >= col || sc < 0||image[sr][sc] != color||visted[sr][sc] )
{
return ;
}
image[sr][sc] = new_color;
visted[sr][sc] = true;
for(int i = 0; i< 4; i++)
{
dfs(image,sr+dx[i],sc+dy[i],new_color);
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int new_color) {
color = image[sr][sc];
row = image.size();
col = image[0].size();
dfs(image,sr,sc,new_color);
return image;
}
};
魔鬼细节
dx dy数组用来干嘛的？
dx dy可以看作 x方向 和 y 方向的向量，sr+dx[i],sc+dy[i] 用来合成四个方向。
我们输入 dx 和 dy 数组时只需要对应位置只有一个零，1和-1的先后顺序不用管
dx={0，1，-1，0} ；
dy = {-1，0，0，1}；
这个数组合成的涵义是 y 方向先 -1 ，x方向 +1 ，x方向-1，y方向+1
visted数组用来干嘛的？
为了避免往复走
从逻辑上每个节点只需要走一次即可
