Problem: Flood Fill Algorithm

*Difficulty: Easy

Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K.

Output:
For each test case print the space separated values of the new matrix.

Constraints:
1<=T<=10
1<=M[][]<=100

Example:
Input:

2
3 4
0 1 1 0 1 1 1 1 0 1 2 3
0 1 5
2 2
1 1 1 1
0 1 8

Output:
0 5 5 0 5 5 5 5 0 5 2 3
8 8 8 8

Implementation: Python 2.7

def floodFill(rootColor, visited, screen, replaceColor, x, y):
    # set color of x,y on the screen
    screen[x][y] = replaceColor
    # mark them as visited
    visited.append((x, y))
    # get all 4 directions 
    # first I make a mistake, I get all 8 directions
    # but in the end, it's wrong
    all_directions = [(x-1, y), (x, y+1),
                        (x+1, y), (x, y-1)]
    # filter those 4 directions
    # only get which one is in screen, not yet visited and has rootColor
    all_directions = filter(lambda coor: isInScreen(coor[0], coor[1], screen) and not (coor[0], coor[1]) in visited and screen[coor[0]][coor[1]] == rootColor , all_directions)
    # recursive call for those all directions
    for (next_x,next_y) in all_directions:
        floodFill(rootColor, visited, screen, replaceColor, next_x, next_y)
    

# check if (x, y) is in screen (not out of bound)
def isInScreen(x, y, screen):
    return x >= 0 and x < len(screen) and y >= 0 and y < len(screen[0])

def printScreen(screen):
    for row in screen:
        for col in row:
            print col,
    print

def main():
    t = input()
    for _ in range(t):
        n, m = map(int, raw_input().strip().split())
        arr = map(int, raw_input().strip().split())
        x, y, replaceColor = map(int, raw_input().strip().split())
        screen, visited = [], []
        # convert list-like array to matrix (actually is a list of list)
        for i in range(0, len(arr), m):
            screen.append(arr[i:i+m])
        rootColor = screen[x][y]
        floodFill(rootColor, visited, screen, replaceColor, x, y)
        printScreen(screen)
        
if __name__ == '__main__':
    main()
Advertisements