python - 使用 DP 优化 rook 移动

Question

车是国际象棋战略棋盘游戏中的一个棋子，它可以水平或垂直移动通过​​任意数量的未占用方格。更正式地说，车可以在以下任一方向 {UP, DOWN, LEFT, RIGHT} 中移动任意数量的方格，直到方格未被占用。

给定车的初始位置(A, B)、最终目的地(C, D) 和棋盘的方向，我们必须找到玩家将车移动到所需目的地所需的最少步数，或者如果棋盘上的所有其他棋子都静止不动，则说这是不可能的。

与普通棋盘不同，对于此问题，棋盘的尺寸为 N x M。棋盘的方向表示为 0/1 二维字符串数组，其中 0 表示空方 block ，1 表示占用方 block 。

我对这个问题的第一次尝试是使用标准 BFS 方法。

from collections import deque
class Solution:

    def solve(self, A, B, C, D, board):
        # @param A, B: (x, y) co-ordinates of start position
        # @param C, D: (x, y) co-ordinates of target position
        # @param board : list of strings
        # @return minimum moves required or impossible

        seen = set()

        def neighbors(i, j):
            @param i, j: co-ordinates of current position
            @return list with all possible valid moves

            nei = []
            x, y = i - 1, j
            while x >= 0 and board[x][y] != '1':
                nei.append((x, y))
                x -= 1

            x, y = i + 1, j
            while x < len(board) and board[x][y] != '1':
                nei.append((x, y))
                x += 1

            x, y = i, j - 1
            while y >= 0 and board[x][y] != '1':
                nei.append((x, y))
                y -= 1

            x, y = i, j + 1
            while y < len(board[0]) and board[x][y] != '1':
                nei.append((x, y))
                y += 1

            return nei

        def bfs(i, j):
            que = deque([(i, j, 0)])

            while que:
                m, n, level = que.popleft()
                seen.add((m, n))

                if m == C and n == D:
                    return level

                for x, y in neighbors(m, n):
                    if (x, y) not in seen:
                        que.append((x, y, level + 1))
                        seen.add((x, y))

            return -1

        return bfs(A, B)

但是这种方法不够有效，因为电路板可能非常大 (~1000x1000)。

在 bfs 方法中进行了大量的重新计算。我将如何编写带内存的 DP 方法？

Answer 1

最短路径问题的动态规划往往看起来就像相关图上的最短路径问题。事实上，在 O(nm) 时间内解决这个问题的一种方法是制作一个图表，其中每个节点不仅代表棋盘上的一个位置，还代表车移动的方向(如果有的话)。图中的每个节点都有到表示相同方向下一个方 block 的节点的零成本弧，以及到表示相同位置但具有其他方向的节点的成本一弧。节点数量增加了 4 倍(起始节点加一)，但邻居数量从 O(n + m) 下降到最多 4，这比您当前的图稀疏得多。

您需要实现类似于 Dijkstra 算法的算法，但您可以使用双向链表代替堆。如果您正在穿越成本为零的弧线，请将头部放在列表的前面。如果要花一个，就把它放在后面。

这是一些寻找邻居的代码(未经测试，使用风险自负)。

# The start node is (x, y, None).
# Returns a list of pairs (neighbor, edge cost).
def neighbors(node, board):
    x, y, direction = node
    if direction is not None:
        dx, dy = direction
        if 0 <= x + dx < len(board) and 0 <= y + dy < len(board[x + dx]) and board[x + dx][y + dy] != '1':
            yield (x + dx, y + dy, direction), 0
    for newdirection in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        if newdirection != direction:
            yield (x, y, newdirection), 1

Python 中的 Dijkstra 通常看起来像这样

import heapq

def dijkstra(source, board):
    heap = [(0, source)]
    distance = {}
    while heap:
        cost, node = heapq.heappop(heap)
        if node in distance:
            continue
        distance[node] = cost
        for neighbor, edgecost in neighbors(node, board):
            heapq.heappush(heap, (cost + edgecost, neighbor))
    return distance

如果 edgecost 总是零-一，那么你可以这样做

import collections

def specialdijkstra(source, board):
    heap = collections.deque([(0, source)])
    distance = {}
    while heap:
        cost, node = heap.popleft()
        if node in distance:
            continue
        distance[node] = cost
        for neighbor, edgecost in neighbors(node, board):
            (heap.append if edgecost else heap.appendleft)((cost + edgecost, neighbor))
    return distance