No.85

$N = 1$ のときは, $M=2$ ならは可能である. $M = 1$ の場合も同様である.

そうでない場合, $N, M$ のいずれかが偶数であれば可能である. $N, M$ がともに奇数であれば不可能である.

$X_0, Y_0$ からスタートしたとすると, 偶数歩歩いたときに $(X_0 + Y_0 \equiv X + Y \pmod 2)$ となる.

$N, M$ がいずれも奇数の場合は $NM$ も奇数であり, すべてのマスを辿ったあとに元のマスに戻るためには奇数歩だけ歩く必要がある. これは上記の条件から不可能である.