MS paint code asked in an interview

Question

I had an interview today and I was asked this question!

code the MS Paint program. Region N * N pixels. given pixel and color, change the color in the pixel to the desired color, and if neighboring pixels have the same color, change them too.

i came up to him, saying that I would take an n * n array and check for a given pixel and move to the next one. for example, the given pixel is x, yi will first check the color in x, y in the array and the next search (x + 1, y + 1), (x + 1, y), (x, y + 1), (x- 1, y), (x-1, Y-1) ....

but the interviewer was not happy, can someone suggest me another way with the best algorithm, which has the best spatial and temporal complexity!

Answer 1

The interviewer probably asked for a flood that could not be done with such a simple approach.

If it is a fill, the diagonal is not considered adjacent.

The simplest fill fill is a recursive call for each adjacent pixel in the array. Using a simple method on a large grid is likely to end from the stack.

The correct way is to paste in the start location, then remove from the queue, check if the pixel color is still a color source, and scan the left and right fill as you move and put all the pixels higher and lower. Continue until the queue runs out.

Answer 2

The algorithm you are talking about is called the fill fill. Known approaches are discussed on Wikipedia.

Answer 3

You can use the DFS algorithm to solve this problem. Given the pixel (xi, yi), you can always construct the graph so that the pixel node (xi-1, yi-1), (xi-1, yi), (xi, yi + 1), (xi + 1, yi), (xi + 1, yi-1), (xi + 1, yi + 1), (xi-1, yi + 1) and (xi, yi-1) as adjacent pixel nodes in (xi, ) Run DFS starting with node (xi, yi), coloring each node in the path and backtrack when you click on a different node color. DFS has good O (V + E) time complexity.