Flood Fill problem

Let's talk about algorithms!

Moderator: Board moderators

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

Flood Fill problem

Post by Roby »

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 »

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)

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

Re: Flood Fill problem

Post by angga888 »

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?

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

Post by Roby »

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 »

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)

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

Post by Roby »

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

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

Post by Roby »

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 »

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 »

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”