We construct a graph with vertices corresponding to the squares, and add a directed edge from \((i,j) \rightarrow (k,l)\) if we can move from square \((i,j)\) to \((k,l)\) to boil down the problem to a shortest path problem from a vertex to each vertex on an unweighted directed graph.

We consider how to enumerate the square that can be movable from square \((i,j)\). It is equivalent to enumerating \((k,l)\) such that \((k-i)^2+(l-j)^2=M\). Since \(|k-i| \le \sqrt{M}\) should hold, \(|k-i| \le \sqrt{M}\).

For a fixed \(k\), we have \(l = j \pm \sqrt{M - (k-i)^2}\).

By precalculating for each integer \(x\) such that \(0 \le x \le M\), whether \(x\) is a square number and if it is, what is \(\sqrt{x}\), in a total of \(\mathrm{O}(M)\) time, to find for a fixed \(k\), whether \(l\) is an integer and if it is, what is the actual value of \(l\), in an \(\mathrm{O}(1)\) time.

Therefore, the transition from each vertex in a BFS (Breadth-First Search) in an \(\mathrm{O}(\sqrt{M})\) time, so the problem can be solved in a total of \(\mathrm{O}(N^2 \sqrt{M})\) time.