棋盘游戏中的识别路径

Question

我的函数采用一个网格矩阵，该矩阵具有有关可用/不可用节点的信息（分别由1/0表示）。如果有一条路径，我将返回最短路径的长度。否则，我返回-1。

我正在尝试以一种这样的方式打印矩阵，使所有作为最短路径一部分的访问节点都标记为'$'而不是'1'。但是，我无法这样做。我该如何调整代码？即使一切似乎正确，它现在也会产生缩进错误。

def shortestPath(grid):
    #print(grid)
    start = (0, 0)
    queue = collections.deque([[start]])
    seen = set([start])
    while queue:
        path = queue.popleft()
        x, y = path[-1]
        if y == 7 and x == 7:
            #print(path)
            for (i, j) in path:
                grid[i][j] = '$'
            print(grid)
            return len(path)
        for x2, y2 in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1), (x - 1, y - 1), (x + 1, y + 1), (x - 1, y + 1), (x + 1, y - 1)):
            if (0 <= x2 < 8) and (0 <= y2 < 8) and (grid[y2][x2] != 0) and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

    print(grid)    
    return -1

这是我试图用'$'代替1的部分：

for (i, j) in path:
                grid[i][j] = '$'

这就是我要传递给函数的内容：

matrix = []
for i in range(8):
    m = []
    for j in range(8):
        m.append(randint(0, 1))
    if i == 0:
        m[0] = 1 
    if i == 7:
        m[-1] = 1
    matrix.append(m)

m = np.array(matrix)               
#print(m)
print(shortestPath(m))

Answer 1

问题在于您如何处理grid：

[寻找下一个可用动作时，请执行此测试：

grid[y2][x2] != 0

(x2, y2)可能添加到路径的位置。

但是当您最终分配$时，您写：

grid[i][j] = '$'

其中(i, j)是从路径中获取的元组。

这是不一致的。您应该在两个grid[][]表达式之一中交换坐标位置以使其一致。