Python:扫雷的floodfill算法

Question

我正在用 Python 编写一个扫雷游戏，目前正在尝试实现一个 floodfill 算法。这是我写的:

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 是一个函数，用于计算 row, col. 周围 8 个方格中的地雷数量。

板 (CURRENT_BOARD) 是列表的列表。

'P'代表一个标志，算法应该跳过标志。

' ' 代表棋盘上的空白区域。

问题是当它被调用时，在它溢出调用堆栈之前我得到了一堆错误，我想知道我做错了什么。

Answer 1

我认为你应该修改你的递归算法:

• 仅在覆盖的瓷砖上操作
• 查找相邻矿山的数量
• 如果有的话，展示一个编号的方 block 并停止递归
• 如果不是，则展示一个空白牌并撤回

您可能还应该考虑如何存放您的电路板。目前您使用板的表示来存储数据。创建一个 tile 类并具有相应打印板的功能可能是个好主意。

至于相邻地雷的数量:地雷永远不会改变，所以你不必一遍又一遍地用一个函数来确定每个瓦片的数量。布下地雷，储存信息后，确定一次就够了。 (如果您为图 block 使用类，我会将信息存储在那里。)

无论如何，下面是一个使用字符串标识加上一组元组位置来表示地雷的实现:

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)