Python: алгоритм floodfill для minesweeper

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

Я думаю, вы должны пересмотреть свой алгоритм рекурсии:

• работать только на крытых плитках
• Находит количество соседних шахт
• Если таковые имеется, показывают пронумерованные плитки и остановка рекурсии
• Если нет, покажите пустую плитку и рекустер

Возможно, вам также следует подумать о том, как вы храните свою доску , На данный момент вы используете представление платы для хранения данных. Это может быть хорошей идеей создать класс плитки и иметь функцию, которая печатает плату соответственно.

Что касается количества соседних мин: шахты никогда не меняются, поэтому вам необязательно определять счетчик для каждой плитки снова и снова с помощью функции. Достаточно определить его один раз после размещения мин и хранения информации. (Если вы используете класс для плитки, я бы хранить информацию там.)

Во всяком случае, ниже реализация, которая использует вашу идентификацию строки плюс набор кортежей позиций представляют мины:

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) 

Answer 2

Следующие выскакивает на меня:

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

Здесь вы рекурсия без изменения платы. Это может быть причиной бесконечной рекурсии, которую вы видите.