DEV Community

faangmaster
faangmaster

Posted on

Задача на обход графа: заливка (Flood Fill)

Нужно реализовать функцию заливки, как в Paint.

Более детально. Дан двумерный массив int image[][]. Значение каждого элемента массива это цвет конкретного пикселя. Также дан заданный цвет и начальная точка заливки. Нужно изменить цвет всех смежных пикселей (и смежных от смежных того же цвета и так далее) на заданный. Смежными считаются пиксели слева, справа, сверху и снизу. По диагонали смежными не считаются.

Пример:

Это классическая задача на обход графа. Например, можно использовать поиск в глубину. Смотри мою статью про DFS.

Представим каждый пиксель как вершину графа. Каждый пиксель имеет 4 соседей: слева, справа, сверху и снизу. Для реализации функции закраски просто будем обходить такой граф при помощи поиска в глубину. Закрасим начальную точку, потом рекурсивно или при помощи стека пойдем в соседние пиксели. Трекать уже посещенные будет при помощи проверки цвета пикселя. Функция visit из моей статьи про DFS это просто изменение цвета пикселя в данном случае. Также нужно добавить условия, что мы не вышли за пределы картинки и что цвет текущего пикселя такой же как и изначальный цвет который мы должны поменять.

Решение с использованием рекурсивной реализации DFS:

    class Solution {
        private static final int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        public int[][] floodFill(int[][] image, int sr, int sc, int targetColor) {
            int sourceColor = image[sr][sc];
            if (sourceColor != targetColor) {
                dfs(image, sr, sc, sourceColor, targetColor);
            }
            return image;
        }

        private void dfs(int[][] image, int r, int c, int sourceColor, int targetColor) {
            //Проверяем, что не вышли за пределы картинки 
            //и клетка нужного цвета sourceColor
            if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] != sourceColor) {
                return;
            }
            image[r][c] = targetColor; //Красим
            for (int[] direction : directions) {
                //Для всех соседних клеток делаем рекурсивный вызов
                dfs(image, r + direction[0], c + direction[1], sourceColor, targetColor);
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

Реализация через стек:

    class Solution {
        private static final int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        public int[][] floodFill(int[][] image, int sr, int sc, int targetColor) {
            int sourceColor = image[sr][sc];
            if (sourceColor != targetColor) {
                dfs(image, sr, sc, sourceColor, targetColor);
            }
            return image;
        }

        private void dfs(int[][] image, int r, int c, int sourceColor, int targetColor) {
            Stack<Integer[]> stack = new Stack<>();
            stack.push(new Integer[] {r, c});
            while (!stack.isEmpty()) {
                Integer[] node = stack.pop();
                image[node[0]][node[1]] = targetColor; //Красим
                for (int[] direction : directions) { //Рассматриваем соседние клетки
                    int neighborRow = node[0] + direction[0];
                    int neighborCol = node[1] + direction[1];
                    //Проверяем, что не вышли за пределы картинки и клетка нужного цвета
                    if (neighborRow >= 0 
                        && neighborCol >= 0 
                        && neighborRow < image.length 
                        && neighborCol < image[0].length 
                        && image[neighborRow][neighborCol] == sourceColor) {
                        stack.push(new Integer[] {neighborRow, neighborCol});
                    }
                }
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More