python - 最短路径数

Question

问题是:

给定输入 n = 4 x = 5，我们必须想象一个横跨(x 轴)4 个方格、高 5 个方格(y 轴)的棋盘。 (这个输入变化，一直到n = 200 x = 200)

然后，我们被要求确定马从棋盘左下角到棋盘右上角的最小最短路径(马可以在一个轴上移动 2 个空间，然后在另一个轴上移动 1 个空间轴)。

我目前的想法:

用一个二维数组存储所有可能的走法，进行广度优先在二维数组上搜索(BFS)以找到最短路径。

Floyd-Warshall 最短路径算法。

创建一个邻接表并对其执行 BFS(但我认为这会很低效)。

老实说，虽然我对逻辑没有真正的把握。

任何人都可以帮助我使用伪代码、python 代码，甚至是问题的逻辑演练吗？

Answer 1

BFS 对于这个问题足够有效，因为它的复杂度是 O(n*x)，因为您只探索每个单元格一次。为了保持最短路径的数量，你只需要保持一个辅助数组来保存它们。

您也可以使用 A* 来更快地解决这个问题，但在这种情况下没有必要，因为这是一个编程竞赛问题。

dist = {}
ways = {}

def bfs():
    start = 1,1
    goal = 6,6

    queue = [start]
    dist[start] = 0
    ways[start] = 1

    while len(queue):
        cur = queue[0]
        queue.pop(0)
        if cur == goal:
            print "reached goal in %d moves and %d ways"%(dist[cur],ways[cur])
            return

        for move in [ (1,2),(2,1),(-1,-2),(-2,-1),(1,-2),(-1,2),(-2,1),(2,-1) ]:
            next_pos = cur[0]+move[0], cur[1]+move[1]
            if next_pos[0] > goal[0] or next_pos[1] > goal[1] or next_pos[0] < 1 or next_pos[1] < 1:
                continue
            if next_pos in dist and dist[next_pos] == dist[cur]+1:
                ways[next_pos] += ways[cur]
            if next_pos not in dist:
                dist[next_pos] = dist[cur]+1
                ways[next_pos] = ways[cur]
                queue.append(next_pos)

bfs()

输出

reached goal in 4 moves and 4 ways

请注意，达到目标的方法数量可能呈指数增长