flood_fill 算法|图形渲染

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数组用来干嘛的？

为了避免往复走
从逻辑上每个节点只需要走一次即可