连接三难题解决

Question

我正在写一个休闲连接三类型的游戏，使用正方形网格。玩家沿着一行或一列滑动（基本上以1D旋转），将至少三个相同类型的块放在一起以便进行匹配。

因为随着比赛的推移难度会增加，随之而来的一个点（我已经检查，这是可能的）的存在是没有动作，这将导致新的比赛。

除了使用蛮力的方法（其为至少O（N^2）时间），是否有寻找可能的移动更快的方法？

Answer 1

你可以做到这一点在O（N日志（M））其中ñ是在董事会和中号位置的数量是形状可供数量：

1. Ø （N日志（M））：对于每一个点（O（N）），更新地图上为它的行和列（O（日志（M））的可用形状
   
2. 。对于每个点（O（N）），检查垂直，水平或对角相邻或相隔一个空间的相似形状（O（1）），并检查行/列图（S）（O（日志（M））），将“连三”，看是否有有效的举措是可用的。

您还可以改进上述方法，以免它不必要地重复检查（第二行及以下的形状不检查，第二列和右侧的形状不检查左侧） ，但大的成本将是相同的。

此外，在每个移动你只需要更新已更改的行/列的地图，你只需要检查已经改变了形状。最坏的情况是，整个板被清除，因此这种改进的大Ø成本将是一样的好。