Я создавал своего рода игру-головоломку.
Правило довольно легко понять, если вы видите короткие превью головоломки.
Предпросмотр 1 Предпросмотр 2
Как видите, у некоторых цветовых блоков есть цветные треугольники. Когда вы щелкаете по треугольнику, он меняет тот же цвет вокруг себя на цвет самого себя.
Цель состоит в том, чтобы объединить целые цветовые блоки в один единственный цветовой блок.
Я пытался найти количество случаев решения головоломки алгоритмически. Поэтому я заменил головоломку на простую структуру данных графа и установил формат ввода.
строка 1) Пара целых чисел v и e: количество вершин и количество ребер
строки 2 ... v + 1) один символ или пара символов: цвет вершины и, если существует, цвет треугольника внутри.
строка v + 2 ... v + e + 1) пара целых чисел: индексы двух вершин, которые должны быть связаны друг с другом. Например,
, график предварительного просмотра 1 может быть показан следующим образом. (каждая вершина указывает от самого левого к правому цветному блоку.)
5 5
A C
B C
C D
D A
C B
0 1
1 2
1 3
2 3
3 4
(Результат должен быть 1. Есть только один способ решить загадку.)
Затем я запрограммировал код в C #; Сделал структуру, которая может указывать каждый цветовой блок, Сделал несколько методов для реализации комбинации нескольких блоков с одинаковыми цветами, меняя цвет блока при нажатии на треугольник ...
Но все, что я могу с ними сделать, это просто перебор всех возможных комбинаций нажатий на каждый треугольник, что займет много времени при решении более сложной головоломки.
Мне нужен более эффективный способ решения проблемы, или я просто хочу знать, есть ли любой алгоритм, который может работать быстрее факторного времени или нет.
Я пробовал динамическое c программирование для повышения производительности, но я не думаю, что проблему можно разбить на более мелкие части, и я не Я не имею ни малейшего понятия, чтобы применить памятку ко всей пачке данных.
Я спрашиваю, есть ли у вас какие-либо идеи, чтобы помочь мне с этой проблемой.
пс. извините, если вам было неудобно читать несовершенный английский sh. Прошло много времени с тех пор, как я опубликовал статью на английском языке sh.