在Python二维数组中判断三个连续元素

Question

我正在用Python制作一个井字棋游戏，棋盘是M x N的大小。我想找一个高效的方法来判断一个玩家是否赢了（也就是在垂直、水平或对角线上连续三个）。大多数3x3的实现方法在每次走棋后都会检查所有可能的获胜组合。但在一个很大的棋盘上，这样做似乎有点过于极端。

4x4的例子：（用1和2代替X和O）

board = ([1,0,2,1], [0,0,0,1], [2,2,0,0], [1,0,0,1])
for row in board:
    print row

谢谢- 乔纳森

Answer 1

检查横向胜利

for row in board:
    rowString = ''.join(row)
    if(rowString.count('111') > 2 or rowString.count('222') > 2):
        print "Somebody won"

检查纵向胜利

for col in xrange(len(board[0])):
    colString = ""
    for row in board:
        colString = colString.append(row[col])
    if(colString.count('111') > 2 or colString.count('222') > 2):
        print "Somebody won"

对斜线的情况还是搞不定...

Answer 2

你可以检查一下玩家的移动是否结束了游戏。具体来说，就是看看那一行、那一列和两个对角线，如果这些地方连续有x个相同的标记（比如都是x），那么就算他赢了。这种检查的复杂度是o(x)。假设你在检查某一行，看看他是否赢了。你可以往左边数有多少个连续的相同标记，然后再往右边数。如果左右两边的数量加起来超过了x个，那就说明他赢了。你也要在列和对角线上做同样的检查。

Answer 3

虽然这种方法听起来有点吸引人，但可能并不是特别快。

# A bogus game with wins in several directions.
board = (
    [1,1,2,1],
    [0,2,1,1],
    [2,2,2,1],
    [1,0,0,1],
)

# A few convenience variables.    
n_rows = len(board)    
lft = [ [0] * i for i in range(n_rows) ]  # [[], [0], [0, 0], [0, 0, 0]]
rgt = list(reversed(lft))

# Create transpositions of the board to check for wins in various directions.
transpositions = {
    'horizontal' : board,
    'vertical'   : zip(*board),
    'diag_forw'  : zip(* [lft[i] + board[i] + rgt[i] for i in range(n_rows)] ),
    'diag_back'  : zip(* [rgt[i] + board[i] + lft[i] for i in range(n_rows)] ),
}

# Apply Jonathan's horizontal-win check to all of the transpositions.
for direction, transp in transpositions.iteritems():
    for row in transp:
        s = ''.join( map(str, row) )
        for player in range(1,3):
            if s.find(str(player) * 3) >= 0:
                print 'player={0} direction={1}'.format(player, direction)

输出：

player=1 direction=diag_back
player=2 direction=diag_forw
player=2 direction=horizontal
player=1 direction=vertical

这个对角线交换的想法是通过移动行来实现的，使用 lft 和 rgt 来进行左右填充。比如，添加填充后，diag_forw 列表看起来是这样的（填充字符用点表示，虽然实际代码中用的是零）。

1 1 2 1 . . .
. 0 2 1 1 . .
. . 2 2 2 1 .
. . . 1 0 0 1 

然后我们只需对这个数组进行转置，使用 zip(*foo)，这样就能利用Jonathan的好主意来寻找横向的胜利。