[Recursion and Dynamic Programming] interview questions #10

[rygh4775]

Paint Fill: Implement the "paint fill" function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.

[tgi01054]

Flood fill Algorithm

References

https://en.wikipedia.org/wiki/Flood_fill https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/ https://www.youtube.com/watch?v=kYqMC3dXC0Q

Source code

// A recursive function to replace previous color 'prevC' at '(x, y)'  
// and all surrounding pixels of (x, y) with new color 'newC' and 
static void floodFillUtil(int screen[][], 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() 
static void floodFill(int screen[][], int x, int y, int newC) 
{ 
    int prevC = screen[x][y]; 
    floodFillUtil(screen, x, y, prevC, newC); 
}