在nxm的游戏板上检查所有可能的长度l线的时间复杂度是多少？
例如，井字板是3x3，线被定义为长度3；有8条可能的线路。我们也可以想象一个9x9的棋盘，规则是你需要一条5长的线才能获胜。您将如何描述检查具有n、m和l的不同值的每一条可能的线的复杂性？
请注意，这不是考虑遍历游戏树进入未来的游戏状态，只是检查棋盘的当前状态，看看在当前状态下是否有赢家。
显然，您需要检查水平线、垂直线和对角线。
让我们假设，如果两者不相等，那么板的布局总是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，那么我们可以再次排除垂直线，但必须考虑对角线。在任何情况下，它都比做对角线、垂直线和水平线要少。
然而，可以根据phantom的评论进行优化。这需要你知道最后一步是什么。
你可以放心地假设，如果采取行动，那是在董事会上没有赢家的时候做出的。因此，如果在移动后棋盘上有获胜条件，那么它一定是最近移动的结果。因此，在给出这些信息的情况下，最坏的情况是，最后的最新动向形成了获胜线。因此，您需要检查在每个方向(水平、垂直、前对角线和后对角线)上延伸l - 1的4条线段。这是4 * (2*l - 1)的总数，将其安全地放入O(l)中。考虑到您只需要存储一个额外的坐标(最近的移动)，这是一个最明智的优化。