Solution


Intuition

As we are looking for a shortest path, a breadth-first search is ideal. The main difficulty is to handle enumerating all possible moves from each square.

Algorithm

Suppose we are on a square with number s. We would like to know all final destinations with number s2 after making one move.

This requires knowing the coordinates get(s2) of square s2. This is a small puzzle in itself: we know that the row changes every N squares, and so is only based on quot = (s2-1) / N; also the column is only based on rem = (s2-1) % N and what row we are on (forwards or backwards.)

From there, we perform a breadth first search, where the nodes are the square numbers s.

Complexity Analysis

  • Time Complexity: , where is the length of the board.

  • Space Complexity: .


Analysis written by: @awice.