我一直在尝试为受游戏“三联镇”启发的问题找到最佳算法。游戏是这样进行的：
您将对象放置在一个网格中，每次您制作一组三个时，它们都会在最后放置的对象的位置凝结成一个更高级别的对象。
此外，如果将其中三个 b 对象放在一起，它们会再次压缩以形成更高级别的对象。
注意：在这些图中，对象的级别表示为 a i、 b i和 c i，下标表示三个一组中的对象编号。
为了简化事情，我只考虑你必须放置的每个对象都是最低级别的。
现在我的问题是：
1：给定x，是否有一种算法可以确定制作x级对象所需的最少网格区域？
例如，a 级需要 1x1，b 级需要 1x3，c 级需要 1x5。
2：给定网格的尺寸，我们能否找到可实现的最高级别和对象数量？
例如，对于 2x2，您可以获得 2 级 'a' 和 2 级 'b'
3：在给定固定网格的情况下，是否有一种算法可以找到对象的最佳顺序和位置以获得尽可能高的级别？
例如，对于 2x2，您可以获得 (1,1),(1,2),(2,2)
4：给定一个预期级别 x 对象的位置，哪一组移动可以最小化制作该对象所需的空间量？
5：这些算法的最佳复杂度是多少？
更新：
我认为在寻找解决方案中突出的一件事是，无法在任何地方完成获取级别 x 的项目。
例如：[ _ _ _ _ c]在固定的 1 x 5 网格中是不可能实现的，因为您需要最后一个 b 在第 5 位，因此您的最后一个 a 在第 5 位。所以要放置第一个 b:[a _ _ _ _]->[a a _ _ _]->[_ _ b _ _]或[_ a _ _ _]->[_ a a _ _]->[_ _ _ b _]. 在这两种情况下，都没有足够的空间来放置 3 个 a 来制作 c 的最后一个 b。
另一件事，我们不能假设任何东西都可以展开为一维网格。这一点在我的下一点中变得很清楚。
我发现了一些有趣的东西：
一个 c 级对象可以在一维网格中与边界的最小接近度。[_ _ a a a]->[_ _ _ b]->[_ a a a b]->[_ _ _ b b]->[a a a b b]->[_ _ c _ _]. 因此，只能在第 3 个位置制作 1 x 5（最佳）网格中的 c 级对象。
由此可见，这是可以由任何数字网格在 1 中制作的最高级别。取 1 乘以无穷大的网格：
..._ a a a _ ... -> ... _ a a a b _ ... -> ... _ a a a b b _ ... -> ... _ c _ ...
现在我们尝试在它旁边直接获取另一个 c：
..._ c a a a _ ... = ... _ c b _ ... or ... _ c _ b _ ... or ... _ c _ _ b _ ...
唯一的选择是..._ c b _ ...因为其他选项无法在 c 和 b 之间形成另一个 b。我们唯一的选择阻止了我们直接在第一个 c 旁边创建 c 的唯一方法，因为它阻止了最后一个 c 去那里。因此，在一维中，c 是我们可以制作的最高级别。换句话说，问题必须在 2 个维度上考虑。