Python | LeetCode
Задача: 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⃣Обновите изображение и верните его.
😎 Решение:
def floodFill(image, sr, sc, color):
original_color = image[sr][sc]
if original_color == color:
return image
def dfs(x, y):
if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or image[x][y] != original_color:
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
Ставь 👍 и забирай 📚 Базу знаний
6 · 609 ·