We might have encountered this at many places. Paint tool is one such example, when we say fill with color in paint, it fills the neighboring areas with the same color.
For examples in the below image when we do a fill color on the white area, we would want all the neighboring white areas to be colored.
The algorithm is very simple. We start with the user selected grid, fill it with color and then check the top, bottom, right and left grid and fill them as well. We do this recursively to achieve the end result.
Below is the procedure
floodFill(vector<vector<int>grid>, x, y, oldColor, newColor)
- If x or y is outside the grid, then return.
- If color of grid[x][y] is not same as oldColor, then return
- do the same for top, down, right and left.
floodFillUtil(grid, x+1, y, oldColor, newColor);
floodFillUtil(grid, x-1, y, oldColor, newColor);
floodFillUtil(grid, x, y+1, oldColor, newColor);
floodFillUtil(grid, x, y-1, oldColor, newColor);
Lets see a C++ implementation for this algorithm
