algorithm - 求解决paint-tool-puzzle的案例数

我正在制作一种绘画工具益智游戏。

如果您看到拼图的简短预览，就很容易理解规则。

如您所见，一些色块具有彩色三角形。当您单击一个三角形时，它会将其周围所有相同的颜色更改为自身的颜色。

目标是将整个色块统一为一个色块。

我试图通过算法找到解决难题的案例数量。所以我用简单的图形数据结构替换了这个难题并设置了输入格式。

第 1 行）整数对 v 和 e：顶点数和边数

第 2...v+1 行）一个字符或一对字符：顶点的颜色，如果存在，内部三角形的颜色。

line v+2...v+e+1) Pair of Integers : 要相互链接的两个顶点的索引。

例如，可以这样显示 Preview 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# 编写了代码；制作了一个可以指示每个颜色块的结构，制作了几种方法来实现几个相同颜色的块的组合，点击三角形时改变块的颜色......

但是我能用它们做的所有事情只是暴力破解点击每个三角形的所有可能组合，这在解决更复杂的难题时将花费大量时间。

我需要更有效的方法来解决问题，或者我只想知道是否有任何算法可以比阶乘时间运行得更快。

我已经尝试过动态编程来提高性能，但我不认为问题可以分解成更小的部分，而且我没有任何线索将 memoiaztion 应用于整个数据。

我问你是否有任何想法可以帮助我解决这个问题。

附言。抱歉，如果您觉得不方便阅读不完善的英语。很久没有发表一篇英文文章了。

标签： algorithm