状態として、

• (先頭, これまで先頭が通ったマスの集合)

を持つことにすると、これは高々 \(2^{36}\cdot 36\) 通りしかないので、ある程度の枝狩りを入れて探索していけば通りそうです。

私は重複する状態を間引くことを忘れてそのまま dfs しましたが、余裕をもって間に合いました。（テストケース数も書いていないので、事前に提出せずに実行時間を見積もりようがないですね…）

コーナーケースとして、体長が \(2\) での場合の \(1\) 歩目の動きに気を付けましょう。これは移動不可能ですが、判定法によっては移動可能と判定してしまいます。