最終更新: 2014-04-25T14:53+0900
迷路より簡単。右下から左上に向かって、右の要素と下の要素を参照しながら順番に処理するだけ。
matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) }
raise "正方行列でない！" if matrix.size != matrix[0].size
(matrix.size-1).downto(0){|i|
(matrix[i].size-1).downto(0){|j|
incr = nil
incr = matrix[i][j+1] if j+1 < matrix[i].size
incr = matrix[i+1][j] if i+1 < matrix.size && (!incr || matrix[i+1][j] < incr)
matrix[i][j] += incr if incr
}
}
p matrix[0][0]
__END__
content of matrix.txt here.
まだまだ簡単。最下段から、行を右へ左へ処理しながら上へ向かうだけ。こういう、問題・入力に依存して可変長のメモリを確保したりしない、そのうえ問題を単純に走査するだけの解法は安心できる。
Matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) }.transpose # transpose:問いの右から左が、下から上への処理になる。
Order = Matrix.size
raise "正方行列でない！" if Matrix.size != Matrix[0].size
row = Matrix[0].dup # 1-line memo. row is now at the first(top) line of Matrix.
1.upto(Order-1){|i|
# move from up ↓↓↓↓↓↓↓↓↓↓
0.upto(Order-1){|j|
row[j] += Matrix[i][j]
}
next if i == Order-1 # 最後の行は横移動不要(※禁止ではない)。最小値だけを選び取って答えにするから。
# move right →→→→→→→→→→
0.upto(Order-2){|j|
src, dst, move_cost = row[j], row[j+1], Matrix[i][j+1]
row[j+1] = src + move_cost if src + move_cost < dst
}
# move left ←←←←←←←←←←
(Order-1).downto(1){|j|
src, dst, move_cost = row[j], row[j-1], Matrix[i][j-1]
row[j-1] = src + move_cost if src + move_cost < dst
}
}
p row.min
__END__
content of matrix.txt here.
Array#transposeを使う機会があるなんて思わなかった！好きなメソッドは transpose(今日だけ)。ま、使わなくてもいいんだけど線形にアクセスするために。ま、メモリ構造からは遠く離れた Rubyなんだけど。
N×N確保していた作業メモを 1行分だけで済ませるようにスクリプトを修正。
コメントに「transpose:問いの右から左が、下から上への処理になる。」ってあるけど、今問題文を見ると左から右になってる。まあ、どっちからどっちでも変わらないからね。問題文が左から右になったからってわけではないけど、アップデート後は上から下の処理に変えてる。下から上だと、どうしてもその必然性を探してしまうから。
シリーズの締め。迷路のときとは違って 80×80ともなると手当たりしだいに探索の手を伸ばしていくと 10分以上の時間がかかる。優先度を付けると insertのコストが加わったにもかかわらず、笑っちゃうぐらい一瞬で終わった。
C++だったら queueの実装として std::multimapを使うところだけど配列をヒープ構造にするのもありだ。
Matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i).freeze }.freeze
raise "正方行列でない！" if Matrix.size != Matrix[0].size
matrix = Matrix.map{|ln| Array.new(ln.size) }
size = matrix.size
moved = lambda{|i,j, l,m|
return false if not (0...size).include?(l) or not (0...size).include?(m)
src, dst, move_cost = matrix[i][j], matrix[l][m], Matrix[l][m]
return false if dst && dst < src + move_cost
matrix[l][m] = src + move_cost
return true
}
matrix[0][0] = Matrix[0][0]
queue = [[0,0]]
insert = lambda{|l,m|
val = matrix[l][m]
queue.insert(queue.index{|i,j| val <= matrix[i][j] }||queue.size, [l,m])
}
until queue.empty?
i,j = *(queue.shift)
break if matrix.last.last and matrix.last.last <= matrix[i][j]
[[i-1,j],[i+1,j],[i, j-1],[i,j+1]].each{|l,m|
if moved[i,j, l,m]
insert[l,m]
end
}
end
p matrix.last.last
__END__
content of matrix.txt here.
<queue>ヘッダには priority_queueクラスがあるし、<algorithm>には make_heap, pop_heap, push_heap といった、配列(RandomAccessIteratorをそなえたコンテナ)にかぶせて使うための関数があった。そりゃあるわなあ。ソートキーが要素のみから算出できない今回の場合に priority_queueを使う(外部キー)か、multimapを使う(内部キー)かはやっぱり決めかねるけど。