Задача: 733. Flood Fill
Сложность: easy

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

👨‍💻 Алгоритм:

1⃣Получите цвет начального пикселя.

2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.

3⃣Обновите изображение и верните его.

😎 Решение:
class Solution {
public:
vector floodFill(vector& image, int sr, int sc, int color) {
int originalColor = image[sr][sc];
if (originalColor == color) {
return image;
}

dfs(image, sr, sc, originalColor, color);
return image;
}

private:
void dfs(vector& image, int x, int y, int originalColor, int newColor) {
if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != originalColor) {
return;
}
image[x][y] = newColor;
dfs(image, x + 1, y, originalColor, newColor);
dfs(image, x - 1, y, originalColor, newColor);
dfs(image, x, y + 1, originalColor, newColor);
dfs(image, x, y - 1, originalColor, newColor);
}
};

Ставь 👍 и забирай 📚 Базу знаний