それぞれのマスに対応する頂点を持つグラフを作り、マス \((i,j)\) からマス \((k,l)\) に移動できるときに \((i,j) \rightarrow (k,l)\) という有向辺を貼ることによって、この問題は有向重み無しグラフに対して、ある頂点からそれぞれの頂点への最短距離を求める問題に帰着します。

マス \((i,j)\) から移動できるマスの列挙を考えます。これは、\((k-i)^2+(l-j)^2=M\) を満たす \((k,l)\) の列挙です。\((k-i)^2 \le M\) を満たす必要があるため、\(|k-i| \le \sqrt{M}\) です。

\(k\) を固定したとき、\(l = j \pm \sqrt{M - (k-i)^2}\) となります。

\(0 \le x \le M\) を満たす整数 \(x\) に対して、\(x\) が平方数であるか、もし平方数であるなら \(\sqrt{x}\) は何かを \(\mathrm{O}(M)\) で前計算しておくことにより、\(k\) を固定したときに \(l\) が整数となるか、\(l\) が整数となるのであればその値は何かを \(\mathrm{O}(1)\) で計算することができます。

よって、BFS である頂点からの遷移を \(\mathrm{O}(\sqrt{M})\) で行うことができるためこの問題を \(\mathrm{O}(N^2 \sqrt{M})\) で解くことができます。