E: Automotive Navigation
問題
二次平面上に軸に平行な辺だけで出来たグラフが与えられる。
グラフ上を一台の車が走る。車はUターンできない。
時刻0での位置と現在時刻tが与えられる。
時刻i(1<=i<=t)のとき次の情報が得られる。
1. 時刻i-1からiまでの移動距離d[i]
2. 時刻iでの方向c[i]（ただし時刻i丁度で方向転換する場合は方向転換する前か後かどちらの可能性もある）
時刻tの車の位置として可能性のある頂点を列挙せよ。
グラフの頂点の座標は0以上50以下の整数座標。
解法
グラフの頂点に方向を付けて、(x, y, dir)のグラフを作る。
現在地としてありえる頂点の集合を一歩ずつ動いて更新することを考える。
交差点では3方向全ての可能性を残す。
d[i]歩動いた時はc[i]でフィルターに掛ける。
つまり
(d[i]歩動いた直後の方向がc[i]に等しい) or (方向転換した後の方向がc[i]に等しい)
ものだけを可能性として残す。
グリッドグラフなのでグラフは隣接リストとか作らず配列だけで扱ったほうが簡単だと思う。
