Код краски MS спросил в интервью

У меня было интервью сегодня, и мне задали этот вопрос!

закодируйте программу MS Paint. Область N * N пикселей. заданный пиксель и цвет, изменить цвет в пикселе на желаемый цвет, и если соседние пиксели имеют одинаковый цвет, измените их тоже.

i подошел к нему, сказав, что я возьму массив n * n и проверил бы для данного пикселя и переместится в соседний. например, заданный пиксель равен x, yi сначала будет проверять цвет в x, y в массиве и следующий поиск (x + 1, y + 1), (x + 1, y), (x, y + 1), (х-1, у), (х-1, Y-1)....

но интервьюер не был доволен, может кто-то предложить мне другой способ с лучшим алгоритмом, который имеет лучшую пространственную и временную сложность!

3 ответа

Интервьюер, вероятно, попросил наводнения, что не может быть сделано с таким простым подходом.

Если это заливка заливки, диагональ не считается смежной.

Простейшая заливка заливки - это рекурсивный вызов для каждого смежного пикселя в массиве. Использование простого способа на большой сетке, скорее всего, закончится со стека.

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


Алгоритм, о котором вы говорите, называется заливом заливки. Известные подходы обсуждаются на Wikipedia.


Для решения этой проблемы вы можете использовать алгоритм DFS. Учитывая пиксель (xi, yi), вы всегда можете построить граф таким образом, чтобы пиксель node (xi-1, yi-1), (xi-1, yi), (xi, yi + 1), (xi + 1, yi), (xi + 1, yi-1), (xi + 1, yi + 1), (xi-1, yi + 1) и (xi, yi-1) в качестве смежных пиксельных узлов в (xi, уг). Выполните DFS, начиная с node (xi, yi), раскрашивая каждый node в пути и обратном следе, когда вы нажмете другой цвет node. DFS имеет хорошую временную сложность O (V + E).

licensed under cc by-sa 3.0 with attribution.