Отклонение цвета графика упражнений в C

Question

Может ли кто-нибудь объяснить мне подход, который я должен использовать для решения этого типа упражнений?

У меня есть карта с 5 областями, и у меня есть 4 цвета: зеленый, красный, желтый иСиний.

Я должен покрасить области с помощью этих 4-х цветов (смежные области НЕ могут иметь одинаковый цвет)

Я должен показать на stdoutвсе возможные решения

Я думал о том, чтобы использовать 2 массива: 1 для областей и 1 для цветов и попробовать все возможные перестановки.Но как я могу установить смежные ограничения в массиве?Спасибо.

Answer 1

Одним из подходов к решению этой проблемы является использование двух матриц:1. Матрица для смежности2. Матрица для раскраски

Подход:

1. Выполните итерацию по всем блокам (областям) с помощью nested loop и примите вход 1, если дваобласти являются смежными, иначе примите вход 0. Сохраните эти значения в своей матрице, соответствующей областямт.е.:

   if(input==1) adjacency[i][j]==adjacency[j][i]==1 else adjacency[i][j]==adjacency[j][i]==0

   Таким образом, у вас будет матрица элементов, показывающая смежность каждого из них.

2. Затем создайте пустойматрица одинакового размера для раскраски.Повторяйте эту матрицу по диагонали (т.е. color[i][i]), назначая цвет (по порядку) областям, а затем проверяйте матрицу смежности для соседних областей.Если области являются смежными (например, adjacency[i][j]==1), проверьте цвет смежной области (например, color[j][j]).Если это то же самое (то есть color[i][i]==color[j][j]), тогда измените свой цвет на следующий цвет и повторите процесс, пока всем областям не будет назначен цвет.

ПРИМЕЧАНИЕ: Это не единственный способ ее решения, и я не могу сказать, что это самый эффективный способ, вы можете выработать лучшую логику, которая будет иметь более низкие временные и пространственные сложности.