奇怪的行为与Python洪水填充算法
问题描述:
我正在实施python扫雷的洪水填充算法。奇怪的行为与Python洪水填充算法
之前,我告诉你的算法,让我定义一些事情是很重要的:
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,它被coverted成蟒索引,(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。这对我来说绝对没有意义,我不知道为什么我会得到这种奇怪的行为。如果您查看其余的输出结果,您也可以看到它在某些点上跳跃了两行索引。
任何人都可以看到算法有什么问题吗?
答
你在说if row < len(BOARD[row])
它正在比较行索引与行(即列数)的长度,而不是行数。同样,您将col
(列索引)与len(BOARD)
进行比较,但len(BOARD)
肯定是行数,而不是列数。
宾果。伟大的发现。用len(BOARD)交换len(BOARD [row]) - 1 - 1的一切工作方式都应该如此。非常感谢。 – JavascriptLoser 2014-11-04 01:06:50