Flood Fill Algorithm

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.

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:

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)