Problem
Again, the solution falls in the bucket of recursion, backtracking.
Method 1 - Recursion
First, let’s visualize how this method works. When we call Paint Fill (eg, “click” paint fill in the image editing application) on, say, a green pixel, we want to “bleed” outwards. Pixel by pixel, we expand outwards calling PaintFill on the surrounding pixel. When we hit a pixel that is not green, we stop. Surrounding green pixels may still be painted if they are touched by another Paint Fill operation.
Java code
References
http://tianrunhe.wordpress.com/2012/03/27/implement-the-paint-fill-function/
Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.Solution
Again, the solution falls in the bucket of recursion, backtracking.
Method 1 - Recursion
First, let’s visualize how this method works. When we call Paint Fill (eg, “click” paint fill in the image editing application) on, say, a green pixel, we want to “bleed” outwards. Pixel by pixel, we expand outwards calling PaintFill on the surrounding pixel. When we hit a pixel that is not green, we stop. Surrounding green pixels may still be painted if they are touched by another Paint Fill operation.
- Base case: the point is at the border. Do nothing.
- Recursion: check the up, down, left and right point to see if we can fill in.
Java code
public static void paintFillRecur(Color[][] screen, int x, int y, Color origin, Color toBeFilled) { if (screen[x][y].equals(origin)) { screen[x][y] = toBeFilled; if (x - 1 >= 0) paintFillRecur(screen, x - 1, y, origin, toBeFilled);//left if (x + 1 < screen.length) paintFillRecur(screen, x + 1, y, origin, toBeFilled);//right if (y - 1 >= 0) paintFillRecur(screen, x, y - 1, origin, toBeFilled);//top if (y + 1 < screen[0].length) paintFillRecur(screen, x, y + 1, origin, toBeFilled);bottom } }
References
http://tianrunhe.wordpress.com/2012/03/27/implement-the-paint-fill-function/
0 comments:
Post a Comment