Python: 扫雷的洪水填充算法

Question

我正在用Python写一个扫雷游戏，现在想实现一个洪水填充算法。这是我写的代码：

def floodfill(CURRENT_BOARD, row, col):
count = count_mines(row, col)
if count in POSSIBLE_MINE_NUMBERS:
    CURRENT_BOARD[row][col] = str(count) + ' '
else:
    if CURRENT_BOARD[row][col] == 'P  ':
        CURRENT_BOARD[row][col] = 'P  '
        if row > 0:
            floodfill(CURRENT_BOARD, row - 1, col)
        if row < len(BOARD[row]) - 1:
            floodfill(CURRENT_BOARD, row + 1, col)
        if col > 0:
            floodfill(CURRENT_BOARD, row, col - 1)
        if col < len(BOARD) - 1:
            floodfill(CURRENT_BOARD, row, col + 1)
    else:
        CURRENT_BOARD[row][col] = '  '
        if row > 0:
            floodfill(CURRENT_BOARD, row - 1, col)
        if row < len(BOARD[row]) - 1:
            floodfill(CURRENT_BOARD, row + 1, col)
        if col > 0:
            floodfill(CURRENT_BOARD, row, col - 1)
        if col < len(BOARD) - 1:
            floodfill(CURRENT_BOARD, row, col + 1)

需要注意的几点：

POSSIBLE_MINE_NUMBERS = [1,2,3,4,5,6,7,8]

count_mines是一个函数，用来计算某个位置周围8个方格里的雷的数量。

棋盘（CURRENT_BOARD）是一个列表的列表。

'P '代表一个旗帜，算法应该跳过这些旗帜。

' '代表棋盘上的一个空格。

问题是每当我调用这个算法时，都会出现很多错误，最后导致调用栈溢出，我在想我哪里做错了。

Answer 1

我注意到以下几点：

if CURRENT_BOARD[row][col] == 'P  ':
    CURRENT_BOARD[row][col] = 'P  '
    ...

在这里，你在进行递归的时候没有对棋盘进行任何修改。这很可能就是你看到的无限递归的原因。

Answer 2

我觉得你应该重新考虑一下你的递归算法：

• 只对已经覆盖的方块进行操作
• 找出周围有多少个地雷
• 如果有地雷，就显示一个带数字的方块，然后停止递归
• 如果没有地雷，就显示一个空白方块，然后继续递归

你可能还需要考虑一下如何存储你的棋盘。目前你是用棋盘的表示方式来存储数据。创建一个方块类，并写一个函数来按照这个类打印棋盘，可能会是个好主意。

关于周围地雷的数量：地雷是不会改变的，所以你不需要每次都用一个函数去计算每个方块的地雷数量。只需在放置地雷后计算一次，然后存储这个信息就可以了。（如果你使用方块类，我建议把这个信息存储在类里面。）

总之，下面是一个实现示例，它使用你的字符串标识和一组元组位置来表示地雷：

Covered = '---'
Flagged = '-P-'

board = []
for x in range(12):
    board += [[Covered] * 12]

mines = set([
    (1, 12), (8, 2), (5, 5), (9, 4), (11, 11), (0, 9),
    (5, 5), (6, 7), (9, 9), (9, 10), (11, 5)
])

def count_mines(a, b):
    c = 0
    if (a - 1, b - 1) in mines: c += 1
    if (a + 0, b - 1) in mines: c += 1
    if (a + 1, b - 1) in mines: c += 1
    if (a - 1, b + 0) in mines: c += 1
    if (a + 1, b + 0) in mines: c += 1
    if (a - 1, b + 1) in mines: c += 1
    if (a + 0, b + 1) in mines: c += 1
    if (a + 1, b + 1) in mines: c += 1
    return c

def floodfill(board, row, col):

    if board[row][col] == Covered:
        count = count_mines(row, col)

        if count > 0:
            board[row][col] = ' ' + str(count) + ' '

        else:
            board[row][col] = '   '

            if row > 0:
                floodfill(board, row - 1, col)
            if row < len(board[row]) - 1:
                floodfill(board, row + 1, col)
            if col > 0:
                floodfill(board, row, col - 1)
            if col < len(board) - 1:
                floodfill(board, row, col + 1)

def show(board):    
    for b in board:
        print "".join(b)

floodfill(board, 0, 0)
show(board)