# Flood fill Algorithm – how to implement fill() in paint?

In MS-Paint, when we take the brush to a pixel and click, the color of the region of that pixel is replaced with a new selected color. Following is the problem statement to do this task.
Given a 2D screen, location of a pixel in the screen and a color, replace color of the given pixel and all adjacent same colored pixels with the given color.

Example:

```Input:
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
x = 4, y = 4, newColor = 3
The values in the given 2D screen indicate colors of the pixels.
x and y are coordinates of the brush, newColor is the color that
should replace the previous color on screen[x][y] and all surrounding
pixels with same color.

Output:
Screen should be changed to following.
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 3, 3, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 3, 3, 0},
{1, 1, 1, 1, 1, 3, 1, 1},
{1, 1, 1, 1, 1, 3, 3, 1},
};
```

Flood Fill Algorithm:
The idea is simple, we first replace the color of current pixel, then recur for 4 surrounding points. The following is detailed algorithm.

```// A recursive function to replace previous color 'prevC' at  '(x, y)'
// and all surrounding pixels of (x, y) with new color 'newC' and
floodFil(screen[M][N], x, y, prevC, newC)
1) If x or y is outside the screen, then return.
2) If color of screen[x][y] is not same as prevC, then return
3) Recur for north, south, east and west.
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC); ```

The following is C++ implementation of above algorithm.

 `// A C++ program to implement flood fill algorithm ` `#include ` `using` `namespace` `std; ` ` `  `// Dimentions of paint screen ` `#define M 8 ` `#define N 8 ` ` `  `// A recursive function to replace previous color 'prevC' at  '(x, y)'  ` `// and all surrounding pixels of (x, y) with new color 'newC' and ` `void` `floodFillUtil(``int` `screen[][N], ``int` `x, ``int` `y, ``int` `prevC, ``int` `newC) ` `{ ` `    ``// Base cases ` `    ``if` `(x < 0 || x >= M || y < 0 || y >= N) ` `        ``return``; ` `    ``if` `(screen[x][y] != prevC) ` `        ``return``; ` ` `  `    ``// Replace the color at (x, y) ` `    ``screen[x][y] = newC; ` ` `  `    ``// Recur for north, east, south and west ` `    ``floodFillUtil(screen, x+1, y, prevC, newC); ` `    ``floodFillUtil(screen, x-1, y, prevC, newC); ` `    ``floodFillUtil(screen, x, y+1, prevC, newC); ` `    ``floodFillUtil(screen, x, y-1, prevC, newC); ` `} ` ` `  `// It mainly finds the previous color on (x, y) and ` `// calls floodFillUtil() ` `void` `floodFill(``int` `screen[][N], ``int` `x, ``int` `y, ``int` `newC) ` `{ ` `    ``int` `prevC = screen[x][y]; ` `    ``floodFillUtil(screen, x, y, prevC, newC); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``int` `screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1}, ` `                      ``{1, 1, 1, 1, 1, 1, 0, 0}, ` `                      ``{1, 0, 0, 1, 1, 0, 1, 1}, ` `                      ``{1, 2, 2, 2, 2, 0, 1, 0}, ` `                      ``{1, 1, 1, 2, 2, 0, 1, 0}, ` `                      ``{1, 1, 1, 2, 2, 2, 2, 0}, ` `                      ``{1, 1, 1, 1, 1, 2, 1, 1}, ` `                      ``{1, 1, 1, 1, 1, 2, 2, 1}, ` `                     ``}; ` `    ``int` `x = 4, y = 4, newC = 3; ` `    ``floodFill(screen, x, y, newC); ` ` `  `    ``cout << ``"Updated screen after call to floodFill: n"``; ` `    ``for` `(``int` `i=0; i

Output:

```Updated screen after call to floodFill:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 3 3 3 3 0 1 0
1 1 1 3 3 0 1 0
1 1 1 3 3 3 3 0
1 1 1 1 1 3 1 1
1 1 1 1 1 3 3 1```

References:
http://en.wikipedia.org/wiki/Flood_fill