Flood Fill

Q: Какова временная сложность алгоритма Flood Fill?

O(m × n) для изображения с m строками и n столбцами. Каждый пиксель области один раз помещается в стек и проверяет четыре соседних пикселя, а пиксели за пределами области рассматриваются только как соседние. Стек может содержать до m × n пикселей, если всё изображение представляет собой одну область.

Q: Что использовать для заливки: BFS или DFS?

Оба варианта работают и требуют времени O(m × n). Область одинакова независимо от порядка обхода, поэтому очередь (поиск в ширину) и стек (поиск в глубину) закрашивают одни и те же пиксели. Выбери тот вариант, который короче записать на твоём языке, и избегай рекурсии для больших изображений.

Q: Почему Flood Fill зацикливается бесконечно, когда новый цвет совпадает со старым?

Обычное решение трактует «всё ещё имеет старый цвет» как «ещё не посещён». Когда новый цвет совпадает со старым, закрашивание пикселя не меняет его, поэтому его соседи снова добавляют его в стек, и поиск не заканчивается. Если сначала проверить этот случай и вернуть изображение, проблема решится, а неизменённое изображение будет правильным ответом.

Q: Можно ли решить заливку рекурсивно?

Да, функция, которая закрашивает пиксель и вызывает себя для каждого соседа старого цвета, верна. Риск заключается в глубине: рекурсия углубляется настолько, насколько длинен самый длинный путь поиска, а в извилистой области это может быть несколько тысяч вызовов. Явный стек выполняет ту же работу без такого ограничения.

ЛегкоГрафы

+10

Изображение — это сетка целых чисел, где каждое число обозначает цвет одного пикселя. Вам дано изображение в виде списка строк, начальный пиксель в строке sr и столбце sc, а также новый color. Перекрасьте область, содержащую начальный пиксель: каждый пиксель того же цвета, что и начальный, до которого можно добраться от него, перемещаясь вверх, вниз, влево или вправо через пиксели того же цвета. Верните изображение после перекрашивания.

Функция

floodFill(image: integer-2d-array, sr: integer, sc: integer, color: integer) → integer-2d-array

imageinteger-2d-array: изображение в виде списка строк, по одному числу на пиксель
srinteger: номер строки начального пикселя, начиная с 0
scinteger: столбец начального пикселя, считая от 0
colorinteger: новый цвет для области
Возвращаетinteger-2d-array: изображение после перерисовки области

Ограничения

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Каждая строка имеет одинаковую длину.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length и 0 ≤ sc < image[0].length

Примеры

Ввод: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Вывод: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Пояснение: В начале находится цвет 1. Единица справа от него, единицы в левом столбце и в нижней строке, а также единица над нижним правым углом связаны с ним, поэтому все семь становятся 5. Два нуля имеют другой цвет и сохраняют его.

+18 скрытых тестов при отправке

Дополнительный вопрос

Как изменилось бы ваше решение, если бы пиксели, соприкасающиеся только углами, тоже считались соединёнными?

Решение

Область — это связная часть графа: пиксели являются узлами, а два пикселя исходного цвета, имеющие общую сторону, соединены. Любой поиск, который начинается с заданного пикселя и проходит только по пикселям этого цвета, находит всю область. Две ловушки — это изображение, в котором новый цвет совпадает со старым, и длинная извилистая область, из-за которой рекурсивный поиск завершается с ошибкой.

Рекурсивный поиск в глубину

Верно, но не успевает на самых больших тестах

Идея

Напиши функцию paint(r, c), которая выполняет одно небольшое действие: если (r, c) находится внутри изображения и в нём всё ещё старый цвет, закрась его новым цветом и вызови себя для четырёх соседей. Один вызов для стартового пикселя распространяется на всю область, потому что каждый пиксель этой области связан со стартовым путём из пикселей старого цвета, а вызовы следуют по этому пути.

Закрашивание пикселя перед четырьмя вызовами не даёт распространению ходить по кругу: когда сосед снова вызывает функцию для уже закрашенного пикселя, цвет больше не совпадает, и вызов сразу завершается. Это работает, только если новый цвет отличается от старого, поэтому сначала проверь это и верни изображение без изменений, если цвета совпадают.

Сложность составляет O(m × n), но слабое место — стек вызовов. Рекурсия углубляется настолько, насколько длинен путь, по которому она проходит. Змейка шириной в один пиксель на изображении 80 × 80 состоит примерно из 3,200 пикселей, поэтому вызовы вложены примерно на 3,200 уровней. По умолчанию Python останавливается на 1,000 и выдаёт ошибку, поэтому этот подход не проходит самые большие тесты. Другие языки допускают более глубокие вызовы, но на изображении большего размера их стек вызовов тоже будет исчерпан.

Алгоритм

Прочитай old = image[sr][sc]. Если old равно color, верни изображение.
Определи paint(r, c): заверши выполнение, если (r, c) находится за пределами изображения или его цвет не равен old.
В противном случае установи image[r][c] = color и вызови paint для пикселей сверху, снизу, слева и справа.
Вызови paint(sr, sc) и верни изображение.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])

    def paint(r, c):
        # Stop outside the image and at any pixel that is not the old color.
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = color
        paint(r + 1, c)
        paint(r - 1, c)
        paint(r, c + 1)
        paint(r, c - 1)

    paint(sr, sc)
    return image

Поиск в глубину с явным стеком

Идея

Выполните тот же обход, но храните пиксели, которые ещё нужно посетить, в собственном стеке, а не в стеке вызовов. Закрасьте начальный пиксель и добавьте его в стек. Извлеките пиксель из стека, проверьте его четырёх соседей и для каждого соседа, который находится внутри изображения и всё ещё имеет старый цвет, закрасьте его и добавьте в стек. Когда стек опустеет, вся область будет закрашена.

Закрашивайте пиксель при добавлении в стек, а не при извлечении. У закрашенного пикселя уже нет старого цвета, поэтому проверка цвета одновременно служит проверкой посещения: ни один пиксель не попадёт в стек дважды, и отдельная сетка отметок не понадобится. Как и в рекурсивной версии, новый цвет должен отличаться от старого, поэтому, если они совпадают, верните изображение без изменений.

Каждый пиксель области добавляется в стек один раз, и для каждого проверяются четыре соседа, поэтому время выполнения составляет O(m × n). В стеке хранится не больше пикселей, чем в самой области. Он находится в обычной памяти, поэтому извилистая область из 3,200 пикселей не станет проблемой, тогда как в рекурсивной версии закончился стек вызовов.

Алгоритм

Считайте old = image[sr][sc]. Если old равно color, верните изображение.
Закрасьте (sr, sc) и поместите его в стек.
Извлеките пиксель из стека и проверьте его четыре соседних пикселя.
Для каждого соседнего пикселя внутри изображения, цвет которого равен old, закрасьте его и поместите в стек.
Когда стек опустеет, верните изображение.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    # Painting a region its own color changes nothing. Returning here also
    # stops the search from pushing the same cells forever.
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
                # Paint on push: a painted cell no longer matches old,
                # so it can never be pushed twice.
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

Ловушки и крайние случаи

Большинство неправильных ответов связано с одним и тем же случаем, когда цвета совпадают, с выходом за пределы изображения или с рекурсией на большой области.

Забывают про случай, когда color совпадает с исходным цветом. Тогда закрашивание ничего не меняет, поэтому поиск, который использует цвет как отметку посещения, бесконечно добавляет в очередь одни и те же пиксели.
Читают image[sr][sc] после того, как закрасили этот пиксель. Сначала сохраните старый цвет, иначе вы будете сравнивать каждого соседа с новым цветом.
Учитывают диагональных соседей. Пиксели, соприкасающиеся только углами, не связаны.
Проверяют цвет соседа, не убедившись, что он находится внутри изображения. Сначала проверьте 0 ≤ row < rows и 0 ≤ col < cols.
Используют рекурсию для большого изображения. Путь шириной в один пиксель через изображение размером 80 × 80 составляет около 3,200 пикселей — этого достаточно, чтобы превысить лимит рекурсии Python.
Закрашивают все пиксели старого цвета во всём изображении. Пиксели этого цвета, отрезанные от начальной точки, должны сохранить свой цвет.

Частые вопросы4

Какова временная сложность алгоритма Flood Fill?

O(m × n) для изображения с m строками и n столбцами. Каждый пиксель области один раз помещается в стек и проверяет четыре соседних пикселя, а пиксели за пределами области рассматриваются только как соседние. Стек может содержать до m × n пикселей, если всё изображение представляет собой одну область.

Что использовать для заливки: BFS или DFS?

Оба варианта работают и требуют времени O(m × n). Область одинакова независимо от порядка обхода, поэтому очередь (поиск в ширину) и стек (поиск в глубину) закрашивают одни и те же пиксели. Выбери тот вариант, который короче записать на твоём языке, и избегай рекурсии для больших изображений.

Почему Flood Fill зацикливается бесконечно, когда новый цвет совпадает со старым?

Обычное решение трактует «всё ещё имеет старый цвет» как «ещё не посещён». Когда новый цвет совпадает со старым, закрашивание пикселя не меняет его, поэтому его соседи снова добавляют его в стек, и поиск не заканчивается. Если сначала проверить этот случай и вернуть изображение, проблема решится, а неизменённое изображение будет правильным ответом.

Можно ли решить заливку рекурсивно?

Да, функция, которая закрашивает пиксель и вызывает себя для каждого соседа старого цвета, верна. Риск заключается в глубине: рекурсия углубляется настолько, насколько длинен самый длинный путь поиска, а в извилистой области это может быть несколько тысяч вызовов. Явный стек выполняет ту же работу без такого ограничения.

Python

def floodFill(image, sr, sc, color):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
sr = 0
sc = 0
color = 5

Ожидается

[[5, 5, 0], [5, 0, 5], [5, 5, 5]]