python - Python flood-fill 算法的奇怪行为

Question

我正在为 python 扫雷器实现一个 flood-fill 算法。

在我展示算法之前，让我定义一些重要的东西:

BOARD，打印漂亮时，看起来像这样:

X 1   1 1 3 X 2 1 2 X 2 2 3 X 2 X X 3 1 2 1 1    
2 2 1 2 X 3 X 3 2 X 2 2 X X 2 3 4 X 4 X 3 X 1    
X 2 1 X 2 3 3 X 2 1 1 1 3 3 2 1 X 2 4 X 4 1 1    
X 2 2 3 3 2 X 4 3 1     1 X 1 1 2 3 4 X 3 1 1 1 1
2 3 2 X X 2 2 X X 1     2 3 3 2 2 X X 3 4 X 2 1 X
X 2 X 3 3 2 3 3 3 2 1 2 2 X X 4 X 3 2 3 X X 2 1 1
1 3 2 2 1 X 2 X 1 2 X 3 X 4 X X 4 3 1 2 X 3 1    
1 2 X 2 2 2 2 1 1 3 X 4 2 3 3 3 X X 3 2 1 1 1 1 1
X 3 1 3 X 2       2 X 2 1 X 1 1 4 X X 1     1 X 2
X 3 1 3 X 2       1 2 2 2 2 2 2 3 X 3 1     2 3 X
2 3 X 2 1 1 1 1 1   1 X 2 2 X 4 X 3 1       1 X 2
X 2 1 1 1 1 2 X 1 1 2 3 X 2 2 X X 2         1 1 1
2 2 1 2 3 X 2 1 1 1 X 2 1 1 1 2 2 2 2 2 1        
X 2 1 X X 3 2 1 1 3 3 2 1 1 1 1 1 2 X X 2        
X 2 1 2 2 3 X 2 1 X X 2 2 X 1 2 X 3 3 X 2   1 1 1
1 2 1 1   2 X 2 2 3 4 X 2 2 2 4 X 3 1 1 1   1 X 1
  1 X 1   2 2 3 2 X 3 2 1 1 X 3 X 2         2 2 2
  1 1 1   1 X 2 X 3 X 1   1 1 2 1 1         1 X 1

显然 X 代表地雷，数字代表该地点周围的地雷数量。空格显然意味着那里没有数字。基本上，BOARD 是我存储信息的方式。

CURRENT_BOARD，打印漂亮时，看起来像这样:

     [A][B][C][D][E][F][G][H][I][J][K][L][M][N][O][P][Q][R][S][T][U][V][W][X][Y]
  [1] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
  [2] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
  [3] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O   
  [4] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
  [5] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
  [6] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
  [7] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
  [8] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
  [9] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [10] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [11] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [12] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [13] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [14] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [15] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [16] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [17] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 
 [18] O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O  O 

零是被覆盖的单元格。 BOARD 和 CURRENT_BOARD 具有相同的行数和列数。

最后，

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

因此，当用户输入行和列值时，例如 1,A，它被转换为 python 索引 (0,0) 并传递给此 floodfill 算法(请注意我用于粗略调试的打印语句)。

def floodfill(CURRENT_BOARD, row, col):
print row
print col
if BOARD[row][col] in POSSIBLE_MINE_NUMBERS:
    CURRENT_BOARD[row][col] = BOARD[row][col] + ' '
else:
    if CURRENT_BOARD[row][col] != '  ':
        CURRENT_BOARD[row][col] = '  '
        if row > 0:
            print 'a'
            floodfill(CURRENT_BOARD, row - 1, col)

        if row < len(BOARD[row]) - 1:
            print 'b'
            floodfill(CURRENT_BOARD, row + 1, col)

        if col > 0:
            print 'c'
            floodfill(CURRENT_BOARD, row, col - 1)

        if col < len(BOARD) - 1:
            print 'd'
            floodfill(CURRENT_BOARD, row, col + 1)

现在，此算法在棋盘底部行(第 17 行)以外的任何位置都可以正常工作。当我尝试在底行运行它时，例如 18, e (17, 4) 我得到以下输出(由于我的调试)(查看最后 3 个):

17
4
16
4
15
4
14
4
a
16
4
b
15
3
c
15
5
d
a
17
4
b
16
3
c
16
5
d
a
18
4

上面写着“a”、18 和 4!所以出于某种原因，floodfill 算法在第一个 if 分支上从 16 跳到 18。这对我来说完全没有意义，我不确定为什么会出现这种奇怪的行为。如果您查看该输出的其余部分，您还可以看到它在某些点跳跃了两个行索引。

有人能看出算法有什么问题吗？

Answer 1

你说的是 if row < len(BOARD[row])这是将行索引与行的长度(即列数)而不是行数进行比较。同样，您正在比较 col ，一个列索引，到 len(BOARD) ，但是len(BOARD)肯定是行数，而不是列数。