Flood Fill Algorithm
Tags: algorithms, python, programming, recursion
Published: 2020-05-23 08:26:27

---
title: Flood Fill Algorithm
published: true
description: 
tags: #algorithms, #python, #programming, #recursion
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/g3e4p5u1qhr0jy66443m.jpg
---
Description
------------

Flood fill also known as Seed Fill algorithm helps us to find connected area to a node in multi dimensional array. It is popularly known for its use in bucket fill tool of paint program to fill similarly colored area and also used in games like Minesweeper, Go etc.

Following animation shows how flood fill algorithm fills area connected to a node with similar color.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/jugf21414se3y6onwaee.gif)

Algorithm
----------

In order to achieve this the algorithm works as follows:

*Input parameters: source_node, color_to_replace, new_color*

Step 1: If color_to_replace is equal to new_color then return.
Step 2: Else If color of source_node is not equal to color_to_replace then return.
Step 3: Else set the source_node color to new_color.
Step 4: Recursively start performing flood fill on following nodes:
- Left node of the source_node, color_to_replace, new_color
- Right node of the source_node, color_to_replace, new_color
- Upper node of the source_node, color_to_replace, new_color
- Node below to the source_node, color_to_replace, new_color

Step 5: return

Implementation
---------------
Let's solve a problem to understand it better.

You're given a image represented as 2D array, row and column of source node and new color. You need to color the source node and all its adjacent node which are similarly colored as source node.

Example 1:
Input: [[1,0,1],[1,1,0],[1,1,1]]
source row = 1, source column = 1 and new color = 2
Output: [[2,0,1],[2,2,0],[2,2,2]]

Example 2:
Input: [[0,0,0],[1,1,0],[1,0,1]]
source row = 1, source column = 1 and new color = 2
Output: [[0,0,0],[2,2,0],[2,0,1]]

Note: Try implementing the algorithm on your own before moving to the solution, it'll surely help 🙂

Solution:
```python
class Solution(object):
    def color_it(self, image, sr, sc, new_color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type new_color: int
        :rtype: List[List[int]]
        """
        # Initiate an array to keep the track of visited elements
        # and color of the elements
        self.image = []

        for i in range(len(image)):
            self.image.append([])
            for j in range(len(image[i])):
                # Keep the track of color and if the node is already visited
                value = {"color": image[i][j], "visited": False}
                self.image[i].append(value)

        current_color = image[sr][sc]

        self.flood_fill(image, sr, sc, current_color, new_color)

        for i in range(len(image)):
            for j in range(len(image[i])):
                image[i][j] = self.image[i][j]["color"]
        return image

    def flood_fill(self, image, row, col, current_color, new_color):
        if row < 0 or row >= len(image) or col < 0 or col >= len(image[0]):
            return

        if image[row][col] != current_color:
            return
        elif image[row][col] == current_color and self.image[row][col]["visited"]:
            return
        elif image[row][col] == current_color and not self.image[row][col]["visited"]:
            self.image[row][col]["color"] = new_color
            self.image[row][col]["visited"] = True

        # Recursively call flood_fill for adjacent nodes
        self.flood_fill(image, row + 1, col, current_color, new_color)
        self.flood_fill(image, row - 1, col, current_color, new_color)
        self.flood_fill(image, row, col + 1, current_color, new_color)
        self.flood_fill(image, row, col - 1, current_color, new_color)
```