140907(2)

Ruby


経路の和（ver.2.0）
テキストファイルに以下のような行列が書かれている。

11,66,55,33, 1

22,20, 1,99, 2

66,46,42,99, 3

99,44,99,96, 4

88,20,99,33,30

44,44,44,44,44

左上から右下までを上下左右方向（ただし、全ての方向を使用しなくてもよい。）
に移動するとき、経路の和の最小値を求めよ。

ver.1.1を少し変更するだけでよい。

a = []
size = 0
ARGF.each_line{|line|
  ary = line.chomp.split(/,/).map(&:to_i)
  @size = ary.size
  a << ary
  size += 1
}
if size < @size
  (@size - size).times{
    a0 = []
    @size.times{a0 << 1.0 / 0}
    a << a0
  }
elsif size > @size
  for i in (0..size - 1)
    (size - @size).times{
      a[i] << 1.0 / 0
    }
  end
else
end

Size = [size, @size].max
b = Array.new(Size){Array.new(Size){1.0 / 0}}

# スタート
si = 0
sj = 0
# ゴール
gi = size - 1
gj = @size - 1

b[si][sj] = a[si][sj]
q = [[si, sj]]
until q.empty?
  i, j = q.pop
  for ni, nj in [
    ([i + 1, j] if i + 1 < Size),
    ([i, j + 1] if j + 1 < Size),
    ([i - 1, j] if i > 0),
    ([i, j - 1] if j > 0)
  ].compact
    if (new_sum = b[i][j] + a[ni][nj]) < b[ni][nj]
      b[ni][nj] = new_sum
      q.unshift([ni, nj])
    end
  end
end

p b[gi][gj]

出力結果
226

ちなみに以下の経路

11,66,55,33, 1

22,20, 1,99, 2

66,46,42,99, 3

99,44,99,96, 4

88,20,99,33,30

44,44,44,44,44


応用
テキストファイルに以下のような行列が書かれている。

11,66,55,33, 1

22,20, 1,99, 2

66,46,42,99, 3

99,44,99,96, 4

88,20,99,33,30

44,44,44,44,44

(1,0)から(4,4)までを上下左右方向（ただし、全ての方向を使用しなくてもよい。）
に移動するとき、経路の和の最小値を求めよ。

上のコードにおいて
# スタート
si = 1
sj = 0
# ゴール
gi = 4
gj = 4
と変更すると、「171」と求まる。

ちなみに以下の経路

11,66,55,33, 1

22,20, 1,99, 2

66,46,42,99, 3

99,44,99,96, 4

88,20,99,33,30

44,44,44,44,44