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

Question

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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