一般的な算出方法を採用しています。ＴＣＯを採用しない方法です（問２と３ＴＣＯを採用しています）。格位置から上、下、右、左への移動を試みます。nextPositions関数はこの四つの移動パタンの中から範囲以内か、又は入るのが可能かどうかという条件を考えて、移動可能な位置を返します。返された位置からすでに通ってある位置が引かれ、次に移動する位置が決まります。
次に移動する位置がなくなったら、ルートの計算終了になります。
入力データが大量であれば、問１のような方法は使えなくなりますので、ＴＣＯを採用した算出方法を使っています。この関数の特徴はスタートからではなく、ゴールからの計算です。格位置がその位置からゴールまでの最高の得点を記憶していますので、毎回毎回それを計算する必要は無くなります。大量のデータでもすばやい計算可能です。
こちらの関数は必要だけな計算をしています。2つの条件が満たされれば、計算終了になります。
- ゴールに到着したルートがある
- ゴールに到着していないルートの中に距離または運賃がより少ないルートはない
距離（又は運賃）の数字が同じルートがあれば、そのルートがすべて返されます（return type はListになります）。
また、ルートを比較するのにOrdering[T]が使われていますので、必要に応じて最小距離とか最小運賃だけでなく、他の比較パタンも利用可能です。
こちらもＴＣＯが採用されています。