各マスを頂点とするグラフを作成する. このとき, \(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 法を用いて計算する.