错误在于试图计算网格上从A点到B点的移动次数.不适用于所有值

Question

我正在进行一项挑战，计算在棋盘一样的网格上从a点到B点所需的移动次数，你可以做出的移动是骑士的移动，所以在任何方向上2次，垂直1次。

我已经解决了大部分问题，但出于某种原因，我的计数器没有返回两点之间的移动次数。以下是我对计票的看法。

你会注意到我使用的是一个名为position的dict，这样做的原因是我可以存储一个int，表示特定位置离目的地的移动次数。

我想最后我应该在移动被认为有效后增加移动值，但我仍然没有得到正确的数字。

def solution(src, dest):
# Chessboard made using nested lists. The indexes will act as coordinates.
chessboard = [
    [0,1,2,3,4,5,6,7],
    [8,9,10,11,12,13,14,15],
    [16,17,18,19,20,21,22,23],
    [24,25,26,27,28,29,30,31],
    [32,33,34,35,36,37,38,39],
    [40,41,42,43,44,45,46,47],
    [48,49,50,51,52,53,54,55],
    [56,57,58,59,60,61,62,63]
    ]
# Find index values of src and dest
for row in chessboard:
    if src in row:
        srcX = chessboard.index(row)
        srcY = row.index(src)
    if dest in row:
        destX = chessboard.index(row)
        destY = row.index(dest)
    
# Position dict to store indexes and no of mvoes when using bfs
position = {
    'x': 0,
    'y': 0,
    'moves': 0,
    }
position['x'] = srcX
position['y'] = srcY
# Below represents the knights moves to be applied to the index of position
row = [-2,-2,-1,1,2,2,1,-1]
col = [-1,1,2,2,-1,1,-2,-2]

# We use an if-statement to check for valid moves 
def isValid(x, y):
    return not (x < 0 or y < 0 or x >=8 or y >=8)
    
q = []
q.append(position)
# Record spaces visited already
isVisited = []
while len(q)>0:
    space = q.pop()
    x = space['x']
    y = space['y']
    moves = space['moves']
    
    
    # if the position matches the destination, return no.moves
    # I'm just using print to see the result in the terminal
    if x == destX and y == destY:
        print(moves)
        
   
    if (x,y) not in isVisited:
        isVisited.append((x,y))
    
        
        # Loop over possible moves
        for i in range(len(row)):
            newX = x + row[i]
            newY = y + col[i]
            
            if isValid(newX, newY):
                position['x'] = newX
                position['y'] = newY
                position['moves'] = moves+1
                q.append(position)

Answer 1

这是一个常见的Python问题。您创建了一个名为"；位置"；并将其添加到队列中。然后，任何时候你有一个新的移动，你修改同一个字典并再次将其添加到队列中，但这并不是创建一个新字典。您最终会得到一个队列，其中充满了对完全相同字典的引用。每次你改变"；位置"；，您正在更改队列中的每个dict。每次都需要创建一个新对象。

这似乎奏效了。

# We use an if-statement to check for valid moves 
def isValid(x, y):
    return (0 <= x <= 7) and (0 <= y <= 7)
def solution(src, dest):
# Chessboard made using nested lists. The indexes will act as coordinates.
    chessboard = [
        [0,1,2,3,4,5,6,7],
        [8,9,10,11,12,13,14,15],
        [16,17,18,19,20,21,22,23],
        [24,25,26,27,28,29,30,31],
        [32,33,34,35,36,37,38,39],
        [40,41,42,43,44,45,46,47],
        [48,49,50,51,52,53,54,55],
        [56,57,58,59,60,61,62,63]
        ]
# Find index values of src and dest
    srcY = src % 8
    srcX = src // 8
    destY = dest % 8
    destX = dest // 8
        
# Position dict to store indexes and no of mvoes when using bfs
    position = {
        'x': srcX,
        'y': srcY,
        'moves': 0,
        }
# Below represents the knights moves to be applied to the index of position
    row = [ -2, -2, -1, -1,  1,  1,  2,  2]
    col = [ -1,  1,  2, -2, -2,  2, -1,  1]
    q = []
    q.append(position)
# Record spaces visited already
    isVisited = []
    while q:
        space = q.pop()
        print( "Checking", space )
        x = space['x']
        y = space['y']
        moves = space['moves']
        
        
        # if the position matches the destination, return no.moves
        # I'm just using print to see the result in the terminal
        if x == destX and y == destY:
            print(f"{moves}!!!")
            return moves
       
        if (x,y) not in isVisited:
            isVisited.append((x,y))
        
            # Loop over possible moves
            for dx,dy in zip(row,col):
                newX = x + dx
                newY = y + dy
                
                if isValid(newX, newY):
                    position = {
                        'x': newX,
                        'y': newY,
                        'moves': moves+1
                    }
                    q.append(position)
print( solution( 3, 61 ) )