140907

Ruby


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

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

左上から右下までを下方向と右方向のみ移動するとき、
経路の和の最小値を求めよ。

昨日のコードでも「236」と求まるが、

より汎用性のあるコードを書いてみた。

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)

  ].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]

ちなみに以下の経路

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)から(2,2)までを下方向と右方向のみ移動するとき、
経路の和の最小値を求めよ。

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

ちなみに以下の経路

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