Задача: 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⃣Обновите изображение и верните его.

😎 Решение:

function floodFill($image, $sr, $sc, $color) {
    $originalColor = $image[$sr][$sc];
    if ($originalColor == $color) {
        return $image;
    }
    
    $dfs = function($x, $y) use (&$image, &$dfs, $originalColor, $color) {
        if ($x < 0 || $x >= count($image) || $y < 0 || $y >= count($image[0]) || $image[$x][$y] != $originalColor) {
            return;
        }
        $image[$x][$y] = $color;
        $dfs($x + 1, $y);
        $dfs($x - 1, $y);
        $dfs($x, $y + 1);
        $dfs($x, $y - 1);
    };
    
    $dfs($sr, $sc);
    return $image;
}

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