No.20
各マスを頂点とするグラフを作成する. このとき, \(x\) 列 \(y\) 行の頂点を \((x, y)\) とする.
まずはオアシスに寄らない場合だが, このときは
\[V - D((0, 0), (N-1, N-1)) \gt 0\]であればゴールに辿り着ける. だたし, \(D((x_1, y_1), (x_2, y_2))\) は2点 \((x_1, y_1), (x_2, y_2)\) の最短距離である.
次にオアシスに寄る場合であるが, このときは
\[(V-D((0, 0), (O_x, O_y))) \times 2 - D((O_x, O_y), (N-1, N-1)) \gt 0\]ならばゴールにた辿り着ける.
\(D\) については Dijkstra 法を用いて計算する.