## 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()

## Reply