检查游戏板上所有可能线路的算法复杂性

Question

在 n x m 的游戏板上检查所有长度为 l 的可能行的时间复杂度是多少？

例如，井字棋盘是 3x3，线的长度定义为 3；有 8 条可能的线。我们还可以想象一个 9x9 的棋盘和一条规则，您需要一条长度为 5 的线才能获胜。您如何描述检查具有不同 n、m 和 l 值的每条可能线的复杂性？

请注意，这不是考虑将游戏树遍历到 future 的游戏状态，只是检查棋盘的当前状态以查看当前状态是否有赢家。

Answer 1

显然，您需要检查水平线、垂直线和对角线。

让我们假设棋盘的布局是，如果两者不相等，n 总是较大的数字，并且它是侧放的”(乐高风格，而不是摩天大楼风格)。所以它是 n 横跨，m 高。

水平线的数量为 n * (m - l)。

垂直线的数量为 m * (n - l)。

对角线将是 (m - l) * (n - l)，或 m*n - l*m - l*n + l*l

如果我们假设 n >= m > l 那么我们可以有把握地说它在 O(n^2) 之内，正如我们所期望的二维董事会。

我们知道 l > n >= m 不会有结果。如果 n = m = l，我们有一个常量 (2*n + 2)。如果 n = l > m 我们还有更好的情况，因为我们不必检查对角线或垂直线，而您只需要检查 m线。如果 n > l > m，那么我们可以再次排除垂直线，但必须考虑对角线。无论如何，它比做对角线、垂直线和水平线要少。

但是，可以根据 phant0m's 进行优化。评论。它要求您知道最后一步是什么。

您可以放心地假设，如果下了一步棋，那是在棋盘上没有赢家的时候下的。因此，如果棋盘上有获胜条件，则它必须是最近一步棋的结果。因此，根据此信息，最坏的情况是获胜线由最后的最近移动形成。因此，您需要检查在每个方向(水平、垂直、前对角线和后对角线)延伸 l - 1 的 4 条线段。这总共是 4 * (2*l - 1)，将它安全地放在 O(l) 中。考虑到您只需要存储一个额外的坐标(最近的移动)，这是最明智的优化。