Нужно реализовать функцию заливки, как в 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});
}
}
}
}
}
Top comments (0)