AOJ 1553 Manhattan Warp Machine 1
解法
ある地点からは、ボタンを押すと正負2つの向きに進むことができてしまうので、単純なDPを行うことができません。
ので、代わりにダイクストラ法で始点から進んでいくと、うまく計算することができます。
コストを辺の重みとみなし、それぞれのボタンについて、
と
に進める、とすると、座標を頂点、ボタンの移動を辺として答えを求めることができます。
座標は、少し多めに確保しておけば、全てのパターンを網羅しきることができます(ボタンの移動の順番は自由に変えられるので、正負をいい感じに交互に織り交ぜることで、配列の外に飛び出さないとたどり着かない、ということがなるなります)。
感想
ICPCを多少やっていたので秒でダイクストラを書き始めることができました。
1ペナを貰ったのは反省です(初期地点の場所を間違えました…)
