Flood Fill problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Flood Fill problem

Post by Roby » Mon Nov 14, 2005 6:44 am

Hello everyone...
Can someone help me convert the usual recursive floodfill function into iterative one? Just pseudocode is OK or the C-function would be better...
Btw, which problem that use floodfill function to solved/finished the problem? I need some... thanx for advance...

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Nov 14, 2005 9:12 am

Convert recursive function into BFS with queue :) It's easy task :)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Re: Flood Fill problem

Post by angga888 » Mon Nov 14, 2005 1:31 pm

Roby wrote:Btw, which problem that use floodfill function to solved/finished the problem? I need some... thanx for advance...
Some problems that can be solved using flood fill:
352 - The Seasonal War
469 - Wetlands of Florida
572 - Oil Deposits
657 - The die is cast
776 - Monkeys in a Regular Forest
782 - Contour Painting
784 - Maze Exploration
785 - Grid Colouring
830 - Shark
852 - Deciding victory in Go
10279 - Mine Sweeper
10336 - Rank the Languages
10592 - Freedom Fighter
10946 - You want what filled?

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Thu Nov 17, 2005 4:17 am

thanx for the reply...
BTW, can someone give me some hints how to construct floodfill function (the usual one) into BFS with queue? I mean the step or pseudocode or something else... hehehe... :D

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Nov 17, 2005 10:06 am

pseudocode for four direction flood-fill algorithm

iterative_floodfill(start_point)
{
- add to queue start_point
- while(length of queue > 0)
- get first element of queue -> qact
- fill this point
- for each direction in which you can go (up, down, left, right)
- check if you visited this point before
- if not => add this point to queue and check, that this point is visited
}

Of course if you know something more about filling, you can try filling in one step as many points as you can (filling for example all points to left and all points to right).

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Thu Nov 17, 2005 12:45 pm

Thanx for the reply... I'll try it... :D

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Tue Nov 22, 2005 6:03 am

Problem 705 - Slash Mazes seems can be solved with floodfill problem, has somebody try to solve it? I just confused with the map given in the problem. How should I interprete it? Any idea... :-?

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: Flood Fill problem

Post by jddantes » Thu Aug 21, 2014 7:09 pm

angga888 wrote:
Roby wrote:Btw, which problem that use floodfill function to solved/finished the problem? I need some... thanx for advance...
Some problems that can be solved using flood fill:
352 - The Seasonal War
469 - Wetlands of Florida
572 - Oil Deposits
657 - The die is cast
776 - Monkeys in a Regular Forest
782 - Contour Painting
784 - Maze Exploration
785 - Grid Colouring
830 - Shark
852 - Deciding victory in Go
10279 - Mine Sweeper
10336 - Rank the Languages
10592 - Freedom Fighter
10946 - You want what filled?
Where did you get the problems that weren't under Graphs in CP3 (Like 830 - shark)?

ayan143
New poster
Posts: 1
Joined: Fri Apr 17, 2015 2:55 pm

Re: Flood Fill problem

Post by ayan143 » Fri Apr 17, 2015 2:57 pm

Of course if you know something more about filling, you can try filling in one step as many points as you can (filling for example all points to left and all points to right).
GuL

Post Reply

Return to “Algorithms”