Задача на обход графа: заливка (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);
            }
        }
    }

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

    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});
                    }
                }
            }
        }
    }