Алгоритм заполнения наводнения

Описание

Заполнение наводнения, также известное как алгоритм заполнения семян, помогает нам найти подключенную область с узлом в многомерном массиве. Он широко известен своим использованием в программе для заполнения ковша, чтобы заполнить аналогично цветную область, а также используется в таких играх, как Minesweeper, Go и т. Д.

Следующая анимация показывает, как алгоритм заполнения наводнения заполняет область, подключенную к узлу с одинаковым цветом.

Алгоритм

Чтобы достичь этого, алгоритм работает следующим образом:

Входные параметры: source_node, color_to_replace, new_color

Шаг 1: Если Color_to_replace равен new_color, верните. Шаг 2: Иначе, если цвет source_node не равен Color_to_replace, затем верните. Шаг 3: Иначе установите цвет исходного_Ноде в new_color. Шаг 4: рекурсивно начните выполнять заполнение наводнения на следующих узлах:

Левый узл исходного_NODE, color_to_replace, new_color
Правый узел Source_node, Color_to_replace, New_color
Верхний узел Source_node, Color_to_replace, New_color
Узел ниже до исходного_NODE, color_to_replace, new_color

Шаг 5: возвращаться

Реализация

Давайте решим проблему, чтобы лучше понять это.

Вам дается изображение, представленное как 2D массив, строку и столбец исходного узла и нового цвета. Вам нужно раскрасить исходный узел и все его соседний узел, которые аналогично окрашены в качестве исходного узла.

Пример 1: Ввод: [[1,0,1], [1,1,0], [1,1,1]] источник, источник и новый выход: [[2,0,1],[2,2,0],[2,2,2]]

Пример 2: Ввод: [[0,0,0], [1,1,0], [1,0,1]] источник, источник и новый выход: [[0,0,0], [2,2,0] , [2,0,1]]]

Примечание. Попробуйте внедрить алгоритм самостоятельно, прежде чем перейти к решению, он, несомненно, поможет 🙂

Решение:

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)

Оригинал: “https://dev.to/ashishpanchal/flood-fill-algorithm-2blj”