Fewer moves to chessboard edge

Question

Today in an exam I was given a algorithmic problem where I was given the size N*M of a chessboard, and I should determine what is the smallest possible number of moves that a knight can do from the bottom left edge of the chessboard to go to the up right edge. How can that be done?

Answer 1

A solution using BFS and 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 can have value -1 or null if we consider the possible distances as a non-negative number [0,+inf).

The minimum number of jumps for each square will be accesible in memo[row][column], so the answer for the top-right corner from the bottom-left will be at memo[N - 1][M - 1].

---

UPDATE

Notice that if the matrix is square N x N, you can apply symmetry principles.