更好的算法检查矩阵中的五连行/列

Question

有没有什么好的算法可以检查一个6x6的方阵中，是否有5个相同的元素在一行、列或者对角线上？

当然可以用一种简单的方法，就是检查每一个位置，然后对每个点，分别查看它所在的行、列和对角线。我在想，是否有更好的方法来实现这个功能。

Answer 1

如果你把行、列和对角线用位图来表示，那么“连五个”就意味着“掩码 % 31 == 0 && 掩码 / 31 == 2的幂”。

• 00011111 表示 0x1f 31（连五个）
• 00111110 表示 0x3e 62（连五个）
• 00111111 表示 0x3f 63（连六个）

如果你想把六个连在一起的情况也当作五个连在一起，最简单的方法可能是：

for ( ; !(mask & 1) ; mask >>= 1 ) {;}
return (mask & 0x1f == 0x1f) ? 1 : 0;

也许斯坦福大学的位操作部门有更好的解决方案或建议，不需要循环？

Answer 2

你可以用一个字典来记录每种元素出现的次数，也就是一个直方图。然后你可以遍历你的行、列或者对角线，每遇到一个元素就把它在字典里的计数加一。最后，你可以检查一下字典里有没有出现5这个数字，或者如果你允许超过5个副本的话，当某个元素的计数达到5时就可以停止了。

这里有个简单的一维示例：

m = ['A', 'A', 'A', 'A', 'B', 'A']

h = {}
for x in m:
    if x in h:
        h[x] += 1
    else:
        h[x] = 1

print "Histogram:", h

for k in h:
    if h[k]>=5:
        print "%s appears %d times." % (k,h[k])

输出结果：

Histogram: {'A': 5, 'B': 1}
A appears 5 times.

简单来说，h[x]会记录元素x在数组中出现的次数（在你的例子里，就是当前的行、列或对角线）。这些元素不需要连续出现，但是每次你开始考虑新的行、列或对角线时，计数都会重置。

Answer 3

你可以在一个整数矩阵中检查是否有 k 个相同的元素，而且只需要一次遍历。

假设 n 是矩阵的大小，m 是矩阵中最大的元素。这个矩阵有 n 列、n 行和 1 条对角线。每一列、每一行或对角线最多有 n 个不同的元素。

现在我们可以创建一个直方图，这个直方图包含 (n + n + 1) * (2 * m + 1) 个元素。这个直方图用来表示行、列和对角线，每个部分最多包含 n 个不同的元素。

size = (n + n + 1) * (2 * m + 1)
histogram = zeros(size, Int)

现在，关键在于如何更新这个直方图？

考虑下面这个伪代码中的函数：

updateHistogram(i, j, element)

    if (element < 0)
        element = m - element;

    rowIndex        = i * m + element
    columnIndex     = n * m + j * m + element
    diagonalIndex   = 2 * n * m + element

    histogram[rowIndex] = histogram[rowIndex] + 1
    histogram[columnIndex] = histogram[columnIndex] + 1

    if (i = j)
        histogram[diagonalIndex] = histogram[diagonalIndex] + 1

接下来，你只需要遍历这个直方图，检查是否有某个元素的数量大于 k。