Flood-fill (node, target-color, replacement-color):
1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.
3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the south of node, target-color, replacement-color).
4. Return.
Flood-Fill & Backtracking
Author
Hi, I've been reading about backtracking algorithms and how I could implement it in a flood-fill scenario. I came across a pseudo-code which was something like:
Say I used a for loop to loop through each of the 4 directions (N,E,S,W), would this approach fit into the category of a backtracking algorithm? Also, does anyone know the Big-O notation of a flood fill algorithm (say the most used implementation), since I've been unable to find it in google? Thanks.
If you're just trying to implement flood-fill on some two-dimensional surface (e.g., the Bucket tool in Paint), a backtracking algorithm is not the right approach. The accepted way is to divide the region into a certain number of subrectangles and then flood-fill each rectangle.
Quote:Original post by steeg
Hi, I've been reading about backtracking algorithms and how I could implement it in a flood-fill scenario. I came across a pseudo-code which was something like:
*** Source Snippet Removed ***
Say I used a for loop to loop through each of the 4 directions (N,E,S,W), would this approach fit into the category of a backtracking algorithm? Also, does anyone know the Big-O notation of a flood fill algorithm (say the most used implementation), since I've been unable to find it in google? Thanks.
That pseudo-code is recursive..
Out of curiosity, k, when would a backtracking algorithm be the right approach?
Author
I know there are better alternatives to backtracking, it's just that I'm doing a paper on this type of algorithms and I wanted to find other possible scenarios for it instead of the ones that appear all over the internet, such as the knight's tour or maze solution.
Also, do you know the Big O notation for a typical flood fill algorihtm, be it implemented as backtracking or other?...Thanks.
Also, do you know the Big O notation for a typical flood fill algorihtm, be it implemented as backtracking or other?...Thanks.
The pseudocode you have above comes directly from wikipedia (http://en.wikipedia.org/wiki/Flood_fill). Have a look at the rest of the page, as it shows pseudocode for more practical applications that don't put your stack at risk.
Author
in the wikipedia page, there ir an animated gif of this algorithm...doesn't it work like an implicit backtracking, since once it cannot move to any other directions (all of the color have already been changed), it returns recursively to previous positions?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement