algorithm - 棋盘边缘的移动更少

Question

今天在一次考试中，我遇到了一道算法题，题目是棋盘的大小 N*M，我应该确定一个马从棋盘左下角可以走的最少步数是多少棋盘去右上边缘。怎么办？

Answer 1

使用 BFS 的解决方案和 memoization :

# Memoization
memo = a matrix of NOVISITED of size N x M

# Starting position
# (row, column, jumps)
queue.push((0, 0, 0))

while queue is not empty:
  # Get next not visited position
  row, column, jumps = queue.pop()

  # Mark as visited
  memo[row][column] = jumps

  for each possible move (nrow, ncolumn) from (row, column):
    if memo[nrow][ncolumn] is NOVISITED:
      # Queue next possible move
      queue.append((nrow, ncolumn, jumps + 1))

NOVISITED 可以有值 -1 或者 null 如果我们将可能的距离视为非负数 [0, +inf).

memo[row][column] 中可以访问每个方 block 的最小跳跃次数，因此从左下角到右上角的答案将在 备忘录[N - 1][M - 1]。

---

更新

请注意，如果矩阵是正方形 N x N，您可以应用对称原理。