Flood Fill

Definition

Flood Fill is a graph algorithm that works well on the grid (but not limited to) to find information about different components of a graph. E.g., find how many connected components are in a grid given walls scattering all over.

It can be easily implemented using recursive approach by making up, down, left, right, four recursive calls. Flood Fill essentially is a DFS algorithm.

Example:

void ff(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >=  m || arr[x][y] != 1)
        return ;
    
    arr[x][y] = 2;
    ff(x+1, y);
    ff(x-1, y);
    ff(x, y+1);
    ff(x, y-1);

}

Note that Flood Fill can take up a lot of stack memories or lead to StackOverflow if the grid size is too large.

The time complexity is usually the size of the grid $O(NM)$

PreviousWormhole Traversal NextGreedy

Last updated 8 months ago

Definition

It can be easily implemented using recursive approach by making up, down, left, right, four recursive calls. Flood Fill essentially is a DFS algorithm.

Example:

void ff(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >=  m || arr[x][y] != 1)
        return ;
    
    arr[x][y] = 2;
    ff(x+1, y);
    ff(x-1, y);
    ff(x, y+1);
    ff(x, y-1);

}

Note that Flood Fill can take up a lot of stack memories or lead to StackOverflow if the grid size is too large.

The time complexity is usually the size of the grid

O(NM)