AOJ 2425 : 全探索お姉さんの休日

A Holiday of Miss Brute Force | Aizu Online Judge

最大何回無視すれば答えがわかるのか、tの上限は?
などと考えて解けないと思っていた。

しかしよく考えてみるとtは6で割った余りだけ保持していれば良いことに気づく。
ある場所にt%6で辿りついたとき、今までのコスト(無視した回数)以下だったら探索しなくて良いので、
状態は cost[x][y][t%6] と取ってコストが小さい順にダイクストラすれば良い。

あとはoffsetを取ったり、隣接しているセルに移動する配列を用意すれば書ける。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2359040#1

abs(x)が奇数だったときに隣接するマスへの差分値が偶数のときと異なることに気づけなくて、
debugするのが大変で時間を喰ってしまった。