Flood Fill

Given a grid of colors, a starting pixel (sr, sc), and a new color, perform a flood fill: change the starting pixel's color and every pixel connected to it (4-directionally) with the same original color to the new color. Print the resulting grid, one row per line, space-separated.

Example

Input:

sr=1, sc=1, newColor=2

Output:

Approach

DFS (or BFS) from the starting cell, only continuing into neighbors that match the original color at the start cell, repainting each as you go. Skip immediately if the new color equals the original (would otherwise infinite-loop).

Input format

Line 1: number of rows R Next R lines: grid row, space-separated Last line: sr sc newColor