1450

NxMの格子点上にある都市において、上下左右斜めの8方向のみに道がある状況で、すべての都市を一度ずつ巡る最短閉路長を求めよ、という問題。

NxM回移動する必要があり、距離1の遷移より短い遷移はない。なので、距離1の遷移のみで一筆書きできるならば、NxMだし、できないならば、NxM+0.41(斜め1回分)になる。一筆書きできないのは、NもMも奇数のときだけ。