Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Problem 83

Project EulerProblem 83(日本語)です。
Problem 81, Problem 82同様、2次元配列$memoに、それぞれのセルまでの和の最小値を格納するようにしています。
最初、再帰を使って解いてみましたが、5x5の例題では解けるものの、80x80だとstack level too deep (SystemStackError)になりますね。
今、注目しているセル(i, j)に、左から到達した場合は以下が実行されることになります。

      when :r
        if memo[i][j-1] + $matrix[i][j] < memo[i][j]
          memo[i][j] = memo[i][j-1] + $matrix[i][j]
          [[i, j+1, :r], [i+1, j, :d], [i-1, j, :u]].each {|e| queue << e }
        end

左のセルへの最短値(memo[i][j-1])と現在の値($matrix[i][j])の和が、今までに求めた最短値よりも小さければ値を置き換えていっています。そしてqueueに次のルートを追加しておきます。次に行くべきところがなくなった(queueが空になった)ら探索終了です。

083.rb