AOJ 1150 - 崖登り - ツバサの備忘録

解法

面倒くさそうに見えますがダイクストラをします。
マス目が少ないので、左のマス目、右のマス目、どちらの足を動かす番か、という情報を全て持ちながらダイクストラができます。
足を動かす際は、動かさない方の足を基準にして、距離と方向を決めます。少し広めに探索して、条件(マンハッタン距離が3以下、等)を満たさなければそこは探索をしない、というようにやってあげると、簡単な2重ループで書けるので楽でした。
また、初期地点は、右足と左足どちらも同じ $S$ のマスにいる、と考えると楽になります。
あとは、丁寧に遷移しながらダイクストラをして、 $T$ につくまでの最短時間を求めれば終わりです。