使用 DP 优化 rook 移动
Optimising rook movement using DP
车是国际象棋战略棋盘游戏中的一个棋子，它可以水平或垂直移动通过任意数量的未占用方格。更正式地说，车可以在以下任一方向 {UP, DOWN, LEFT, RIGHT} 中移动任意数量的方格，直到方格未被占用。
给定车的初始位置(A, B)、最终目的地(C, D)和棋盘的方向，我们必须找到玩家移动车所需的最少步数将车开到想要的目的地，或者说这是不可能的，前提是棋盘上的所有其他棋子都是静止的。
与普通棋盘不同，对于此问题，棋盘的尺寸为 N x M。棋盘的方向表示为 0/1 二维字符串数组，其中 0 表示空方块并且 1 表示占用的正方形。
我第一次尝试解决这个问题是使用标准 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 方法？
最短路径问题的动态规划往往看起来就像相关图上的最短路径问题。事实上，在 O(nm) 时间内解决这个问题的一种方法是制作一个图表，其中每个节点不仅代表棋盘上的一个位置，还代表车移动的方向（如果有的话）。图中的每个节点都有到表示相同方向下一个方块的节点的零成本弧，以及到表示相同位置但具有其他方向的节点的成本一弧。节点数量增加了 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
Dijkstra 在 Python 中通常看起来像
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总是0-1，那么你可以
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
我可能会尝试一些更接近于填充的东西，使用板本身作为智能访问结构，可能会忽略节点的方向。我们知道任何二维 space 都被两个车移动覆盖。例如，从 A 到 B （X 的块，点是免费的）：
..1...XXX....
11A11XXXXX...
XX1...XXXX..X
XXXX.X..XXX..
XXXX..XXX....
XXXXX...B..XX
每个 1 都被推入队列并辐射到相同（下一个）级别或未访问的单元格。
221222XXX....
11A11XXXXX...
XX1222XXXX..X
XXXX2X..XXX..
XXXX2.XXX....
XXXXX...B..XX
重复下一关
221222XXX....
11A11XXXXX...
XX1222XXXX..X
XXXX2X..XXX..
XXXX23XXX....
XXXXX...B..XX
...
221222XXX....
11A11XXXXX...
XX1222XXXX..X
XXXX2X..XXX..
XXXX23XXX....
XXXXX455B..XX
粗略 Python 草稿（缺少被阻止的单元格检查）：
from collections import deque
def f(a, b, c, d, board):
queue = deque([(a, b, 1)])
board[a][b] = 'S'
while queue:
(y, x, level) = queue.popleft()
if y == c and x == d:
board[c][d] = 'E'
for row in board:
print "".join(map(lambda x: str(x), row))
return level - 1
level = level + 1
# up
yy = y - 1
while yy >= 0 and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy - 1
# down
yy = y + 1
while yy < len(board) and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy + 1
# left
xx = x - 1
while xx >= 0 and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx - 1
# right
xx = x + 1
while xx < len(board[0]) and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx + 1
a = 1
b = 2
c = 5
d = 8
M = [
[char for char in "0000001110000"],
[char for char in "0000011111000"],
[char for char in "1100001111001"],
[char for char in "1111010011100"],
[char for char in "1111001110000"],
[char for char in "1111100000011"]
]
print f(a, b, c, d, M)
输出：
3323331110000
22S2211111000
1123331111001
1111310011100
1111341110000
11111566E6611
5
更新
这是传递代码：
from collections import deque
class Solution:
# @param A : integer
# @param B : integer
# @param C : integer
# @param D : integer
# @param E : list of strings
# @return an integer
def solve(self, a, b, c, d, board):
board = map(lambda x: [char for char in x], board)
a = a - 1
b = b - 1
c = c - 1
d = d - 1
queue = deque([(a, b, 1)])
while queue:
(y, x, level) = queue.popleft()
if y == c and x == d:
return level - 1
level = level + 1
# up
yy = y - 1
while yy >= 0 and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy - 1
# down
yy = y + 1
while yy < len(board) and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy + 1
# left
xx = x - 1
while xx >= 0 and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx - 1
# right
xx = x + 1
while xx < len(board[0]) and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx + 1
return -1
车是国际象棋战略棋盘游戏中的一个棋子，它可以水平或垂直移动通过任意数量的未占用方格。更正式地说，车可以在以下任一方向 {UP, DOWN, LEFT, RIGHT} 中移动任意数量的方格，直到方格未被占用。
给定车的初始位置(A, B)、最终目的地(C, D)和棋盘的方向，我们必须找到玩家移动车所需的最少步数将车开到想要的目的地，或者说这是不可能的，前提是棋盘上的所有其他棋子都是静止的。
与普通棋盘不同，对于此问题，棋盘的尺寸为 N x M。棋盘的方向表示为 0/1 二维字符串数组，其中 0 表示空方块并且 1 表示占用的正方形。
我第一次尝试解决这个问题是使用标准 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 方法？
最短路径问题的动态规划往往看起来就像相关图上的最短路径问题。事实上，在 O(nm) 时间内解决这个问题的一种方法是制作一个图表，其中每个节点不仅代表棋盘上的一个位置，还代表车移动的方向（如果有的话）。图中的每个节点都有到表示相同方向下一个方块的节点的零成本弧，以及到表示相同位置但具有其他方向的节点的成本一弧。节点数量增加了 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
Dijkstra 在 Python 中通常看起来像
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总是0-1，那么你可以
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
我可能会尝试一些更接近于填充的东西，使用板本身作为智能访问结构，可能会忽略节点的方向。我们知道任何二维 space 都被两个车移动覆盖。例如，从 A 到 B （X 的块，点是免费的）：
..1...XXX....
11A11XXXXX...
XX1...XXXX..X
XXXX.X..XXX..
XXXX..XXX....
XXXXX...B..XX
每个 1 都被推入队列并辐射到相同（下一个）级别或未访问的单元格。
221222XXX....
11A11XXXXX...
XX1222XXXX..X
XXXX2X..XXX..
XXXX2.XXX....
XXXXX...B..XX
重复下一关
221222XXX....
11A11XXXXX...
XX1222XXXX..X
XXXX2X..XXX..
XXXX23XXX....
XXXXX...B..XX
...
221222XXX....
11A11XXXXX...
XX1222XXXX..X
XXXX2X..XXX..
XXXX23XXX....
XXXXX455B..XX
粗略 Python 草稿（缺少被阻止的单元格检查）：
from collections import deque
def f(a, b, c, d, board):
queue = deque([(a, b, 1)])
board[a][b] = 'S'
while queue:
(y, x, level) = queue.popleft()
if y == c and x == d:
board[c][d] = 'E'
for row in board:
print "".join(map(lambda x: str(x), row))
return level - 1
level = level + 1
# up
yy = y - 1
while yy >= 0 and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy - 1
# down
yy = y + 1
while yy < len(board) and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy + 1
# left
xx = x - 1
while xx >= 0 and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx - 1
# right
xx = x + 1
while xx < len(board[0]) and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx + 1
a = 1
b = 2
c = 5
d = 8
M = [
[char for char in "0000001110000"],
[char for char in "0000011111000"],
[char for char in "1100001111001"],
[char for char in "1111010011100"],
[char for char in "1111001110000"],
[char for char in "1111100000011"]
]
print f(a, b, c, d, M)
输出：
3323331110000
22S2211111000
1123331111001
1111310011100
1111341110000
11111566E6611
5
更新
这是传递代码：
from collections import deque
class Solution:
# @param A : integer
# @param B : integer
# @param C : integer
# @param D : integer
# @param E : list of strings
# @return an integer
def solve(self, a, b, c, d, board):
board = map(lambda x: [char for char in x], board)
a = a - 1
b = b - 1
c = c - 1
d = d - 1
queue = deque([(a, b, 1)])
while queue:
(y, x, level) = queue.popleft()
if y == c and x == d:
return level - 1
level = level + 1
# up
yy = y - 1
while yy >= 0 and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy - 1
# down
yy = y + 1
while yy < len(board) and (board[yy][x] == '0' or board[yy][x] == level):
if board[yy][x] == '0':
queue.append((yy, x, level))
board[yy][x] = level
yy = yy + 1
# left
xx = x - 1
while xx >= 0 and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx - 1
# right
xx = x + 1
while xx < len(board[0]) and (board[y][xx] == '0' or board[y][xx] == level):
if board[y][xx] == '0':
queue.append((y, xx, level))
board[y][xx] = level
xx = xx + 1
return -1