识别矩阵游戏中的路径

Question

我正在 return计算最短路径的长度（如果有的话）。否则，我return -1.

我正在尝试以这样一种方式打印矩阵，即所有作为最短路径一部分的已访问节点都标有“$”而不是“1”。但是，我无法这样做。

def Path(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):
            if (grid[y2][x2] != 0) and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

    print(grid)    
    return -1

Answer 1

问题在于您如何处理 grid:

寻找下一个可用的着法时，你做这个测试：

grid[y2][x2] != 0

其中 (x2, y2) 可能添加到路径中。

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

grid[i][j] = '$'

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

这不一致。您应该交换两个 grid[][] 表达式之一的坐标位置，使它们保持一致。