Description:
各面に1から50までのどれかが書かれた6面サイコロと、縦幅4マスで横幅無限マスのフィールドがある。
このフィールドからはみ出さないように、スタートからゴールまで、サイコロを滑らないように転がしながら移動する。
サイコロを移動させるのには、移動後のサイコロの上を向いている面に書かれた数字の分だけコストが掛かる。
スタートからゴールまでの移動コストの総和を最小化せよ。
スタートとゴールのx座標は、-10億以上10億以下。
Answer:
ダイクストラでスタート近くのマスに対して答えを十分な幅全て求める。
マス(X,Y)のスコアをS(X,Y)と表現すると、スタートから十分離れた所では、S(X,Y)=S(X-A,Y)+Bが成り立つはずなので、
このようなA,Bを探す。
Source: