## Flood Fill problem

Moderator: Board moderators

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

### Flood Fill problem

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:
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

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:
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...

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
pseudocode for four direction flood-fill algorithm

iterative_floodfill(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:
Thanx for the reply... I'll try it...

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
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

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

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