我已经坐了几乎一个星期了.以下是PDF格式的问题.
到目前为止,我只能想到一个想法,但它失败了.我的想法是递归地创建所有连接的子图,这些子图在O(num_of_connected_subgraphs)中工作,但这太慢了.
我真的很感谢有人给我一个方向.我倾向于认为唯一的方法是动态编程,但我似乎无法弄清楚如何去做.
好的，这是我提出的算法的概念描述：
在两个维度上形成一个从 -7 到 7 的 (x,y) 棋盘地图数组，并将对手的棋子放在上面。
从第一行开始（最低 Y 值，-N）：
枚举该行第二个玩家棋子的所有可能组合，仅消除与对手棋子冲突的组合。
对于该行上的每个组合： --将连接的部分分组到单独的网络中，并将这些网络从 1 开始升序编号
--使用以下方法将行编码为向量：
= 0 for any unoccupied or opponent position
= (1-8) for the network group that that piece/position is in.
--给每个这样的分组 COUNT 1，并使用编码向量作为其键将其添加到字典/哈希集中
现在，对于每个后续行，按升序排列 {y=y+1}：
对于前一行字典中的每个条目：
--如果条目正好有 1 个组，则将其 COUNT 添加到 TOTAL
--枚举当前行第二个玩家棋子的所有可能组合，仅消除与对手棋子冲突的组合。（更改：）您应该跳过此步骤的初始组合（其中所有条目均为零），因为上面的步骤实际上涵盖了它。对于当前行上的每个此类组合：
+ produce a grouping vector as described above
+ compare the current row's group-vector to the previous row's
group-vector from the dictionary:
++ if there are any group-*numbers* from the previous row's
vector that are not adjacent to any gorups in the current
row's vector, *for at least one value of X*, then skip
to the next combination.
++ any groups for the current row that are adjacent to any
groups of the previous row, acquire the lowest such group
number
++ any groups for the current row that are not adjacent to
any groups of the previous row, are assigned an unused
group number
+ Re-Normalize the group-number assignments for the current-row's
combination (**) and encode the vector, giving it a COUNT equal
to the previous row-vector's COUNT
+ Add the current-row's vector to the dictionary for the current
Row, using its encoded vector as the key. If it already exists,
then add it's COUNT to the COUNT for the pre-exising entry
最后，对于字典中最后一行的每个条目：
**：重新归一化简单地意味着重新分配组编号，以消除分组模式中的任何排列。具体来说，这意味着新的组编号应按从左到右、从 1 开始的递增顺序分配。例如，如果您的分组向量在将 ot 分组到上一行后看起来像这样：
2 0 5 5 0 3 0 5 0 7 ...
它应该被重新映射到这个范式：
1 0 2 2 0 3 0 2 0 4 ...
请注意，如本例所示，在第一行之后，分组可能是不连续的。这种关系必须被保留，因此两组“5”在重新归一化中被重新映射到相同的数字（“2”）。
好的，有几点注意事项：
答：我认为这个做法是正确的，但我真的不确定，所以肯定需要一些审查等。
B. 虽然很长，但还是很粗略。每个单独的步骤本身都很重要。
C. 虽然有很多单独的优化机会，但整体算法仍然相当复杂。它比暴力破解要好得多，但即便如此，我的餐巾纸后估计仍然约为 N=7 的 (2.5 到 10)*10^11 次操作。
所以它可能很容易处理，但距离 3 秒内完成 74 个案例还有很长的路要走。我还没有阅读 Peter de Revaz 答案的所有细节，但他旋转“钻石”的想法可能对我的算法可行。虽然它会增加内部循环的复杂性，但它可能会将字典的大小（以及要比较的分组向量的数量）减少 100 倍之多，尽管如果不实际尝试的话很难说清楚。
好的，我枚举了所有可能的有效分组向量，以更好地估计上面的 (C)，这将 N=7 的情况降低到 O(3.5*10^9)。这要好得多，但仍然比您在 3 秒内完成 74 项测试可能需要的量高出一个数量级。但这确实取决于测试，如果大多数测试都小于 N=7，它可能能够成功。