Scribd
Upload
4 views

Flood-fill Algorithm Tutorials

Uploaded by

Mamat Rahmat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

Flood-fill Algorithm Tutorials

Uploaded by

Mamat Rahmat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Signup and get free access to 100+ Tutorials and Practice Problems Start Now

All Tracks  Algorithms  Graphs  Flood-fill Algorithm

Algorithms

 Solve any problem to achieve a rank


View Leaderboard

Topics: Flood-fill Algorithm 

Flood-fill Algorithm
Problems Tutorial

Flood fill algorithm helps in visiting each and every point in a given area. It determines the area connected to a
given cell in a multi-dimensional array. Following are some famous implementations of flood fill algorithm:

Bucket Fill in Paint:


Clicking in an area with this tool selected fills that area with the selected color.

Solving a Maze:
Given a matrix with some starting point, and some destination with some obstacles in between, this algorithm
helps to find out the path from source to destination

Minesweeper:
When a blank cell is discovered, this algorithm helps in revealing neighboring cells. This step is done recursively till
cells having numbers are discovered.

Flood fill algorithm can be simply modeled as graph traversal problem, representing the given area as a matrix
and considering every cell of that matrix as a vertex that is connected to points above it, below it, to right of it,
and to left of it and in case of 8-connections, to the points at both diagonals also. For example, consider the
image given below.
It clearly shows how the cell in the middle is connected to cells around it. For instance, there are 8-connections
like there are in Minesweeper (clicking on any cell that turns out to be blank reveals 8 cells around it which
contains a number or are blank). The cell is connected to
.

In general any cell is connected to


. Of course, the boundary conditions are to be kept in mind.

Now that the given area has been modeled as a graph, a DFS or BFS can be applied to traverse that graph. The
pseudo code is given below.

function DFS(x, y, visited, n, m)


if (x ≥ n OR y ≥ m)
return
if(x < 0 OR y < 0)
return
if(visisted[x][y] == True)
return
visited[x][y] = True
DFS(x-1, y-1, visited, n, m)
DFS(x-1, y, visited, n, m)
DFS(x-1, y+1, visited, n, m)
DFS(x, y-1, visited, n, m)
DFS(x, y+1, visited, n, m)
DFS(x+1, y-1, visited, n, m)
DFS(x+1, y, visited, n, m)
DFS(x+1, y+1, visited, n, m)

The above code visits each and every cell of a matrix of size starting with some source cell. Time
Complexity of above algorithm is .

One another use of flood algorithm is found in solving a maze. Given a matrix, a source cell, a destination cell,
some cells which cannot be visited, and some valid moves, check if the destination cell can be reached from the
source cell. Matrix given in the image below shows one such problem.
The source is cell and the destination is cell . Cells containing cannot be visited. Let's assume there
are valid moves - move up, move down, move left and move right.

Following pseudo code solve the problem given above.

function DFS(x, y, visited, n, m, mat, dest_x, dest_y)


if(x == dest_x AND y == dest_y)
return True
if(x ≥ n OR y ≥ m)
return False
if(x < 0 OR y < 0)
return False
if(visisted[x][y] == True)
return False
if(mat[x][y] == X)
return False
visited[x][y] = True
if (DFS(x+1, y, visited, n, m, mat, dest_x, dest_y) == True)
return True
if (DFS(x-1, y, visited, n, m, mat, dest_x, dest_y) == True)
return True
if (DFS(x, y+1, visited, n, m, mat, dest_x, dest_y) == True)
return True
if (DFS(x, y-1, visited, n, m, mat, dest_x, dest_y) == True)
return True
return False

The code given above is same as that given previously with slight changes. It takes three more parameters
including the given matrix to check if the current cell is marked or not and coordinates of destination cell
. If the current cell is equal to destination cell it returns True, and consequently, all the previous
calls in the stack returns True, because there is no use of visiting any cells further when it has been discovered
that there is a path between source and destination cell.

So for the matrix given in image above the code returns True.
If, in the given matrix the cell was also marked , then the code would have returned False, as there
would have been no path to reach from to in that case.
Contributed by: Vaibhav Jaimini

Did you find this tutorial helpful? 


 Yes

 No

TEST YOUR UNDERSTANDING

Micro and Maze

Micro just bought a maze, that can be represented as a matrix A of size , where rows are numbered from
1 to N and columns are numbered from 1 to M. Each cell of the matrix can be either 0 or 1. If a cell is 0, that
means it cannot be visited and if it is 1, then it can be visited. Allowed moves are up, down, left and right. Help
Micro to find out if he can reach from the cell to the cell , it is guaranteed that the cells and
have value 1.

Input:
First line consists of a two space separated integers denoting N and M.
Following N lines consists of M space separated integers denoting the matrix A.

Output:
Print "Yes" (without quotes), if Micro can reach from cell to otherwise print "No" (without quotes).

Constraints:

SAMPLE INPUT  

3 3
1 0 1
1 0 0
1 1 1

SAMPLE OUTPUT  

Yes

Enter your code or Upload your code as file. Save C (gcc 10.3)  
1 #include <stdio.h>
2
3 int main(){
4 int num;
5 scanf("%d" &num); // Reading input from STDIN

You might also like