c++ - 找到由三角形组成的六边形的最大外侧总和

Question

我有三角形的问题。

我有 6 个三角形，例如：

每个三角形的每一边都有一个值。问题是我可以移动三角形并且可以旋转它们。我必须像这样创建一个六边形：

我必须添加三角形的外侧并获得最高分。在此示例中为 152。

并且内侧必须相等
，例如 3 与 3、2 与 2、5 与 5、7 与 4 与 4 以及 1 与 1。

我在 C++ 中这样做。

我将每个三角形保存在一个数组中。

int triangle[6][3];
for(int i=0;i<6;i++)
    cin>>triangle[i][0]>>triangle[i][1]>>triangle[i][2];

我打算将数组的最后一个元素与其他元素进行比较，但它不起作用。

谁能给我一个想法来解决这个问题？因为我不知道如何为三角形生成所有可能的组合来创建六边形，以及其他时间不在同一个数组中搜索的方法，以及如何添加才能获得分数。

可能存在无法形成六边形的情况。

最后一个元素可能是我无法形成三角形，那么我需要旋转三角形来形成六边形。

score 1 · Accepted Answer

这是一个算法：

选择一个三角形。称它为A。（在本例中为 1-4-20 三角形。）

遍历A的边；选择一侧（例如 1）并假设它是外侧。下一条边 (4) 必须是内侧，因此请找出可以匹配该边的所有其他三角形（在本例中只有一个，4-7-50）。遍历此列表，寻找下一个内侧 (50) 的匹配项。继续，直到您找到所有可能的六边形来选择A的一侧。

遍历A的所有边并找到所有可能的六边形后，选择得分最高的一个。

这其中有困难的部分吗？您需要数据结构方面的帮助吗？

编辑：

我建议学习更好的数组容器，但这可能是另一天。

该函数应接受两个数组作为参数，并返回一个。（也许还有一些数字来表示数组的长度。）这两个参数是 1）部分六边形，2）其余的三角形。返回值是可以从中得到的最佳六边形；它可能是空的。

假设我们用

{(3,1,5)}, {(1,4,20), (50,2,3), (5,2,7), (7,5,20), (4,7,50)}

该函数查找 5 的匹配项，并找到两个可能的匹配项：(5,2,7) 和 (5,20,7)。所以它进行了两次递归调用，

{(3,1,5), (5,2,7)}, {(1,4,20), (50,2,3), (7,5,20), (4,7,50)}

和

{(3,1,5), (5,20,7)}, {(1,4,20), (50,2,3), (5,2,7), (4,7,50)}

它从这些调用中（最多）接收两个六边形，比较它们，并返回更好的一个。

score 1 · Accepted Answer

我会发展这个逻辑。你写代码。

2 回答 2