Project Euler 83

プロジェクトオイラー
http://projecteuler.net/index.php

Q83.
与えられた行列の左上から右下へのルートの総和の最小

左上からの最小和を調べていく。調べられたマスのうち、隣にまだ調べられていないマスがあるマスのうち最小のものを得て、その隣のマスにそれ＋そのマスの数字を書く。うまく説明できないが、詳しくはコード。

def val(x):

    return a[x[1] ][x[0] ]
neighbors = [ (1, 0), (0, 1), (-1, 0), (0, -1) ]
def is_in_region(x):

    return 0 <= x[0] and x[0] < M and 0 <= x[1] and x[1] < N
def is_interface(x):

    if d[x[1] ][x[0] ] < 0:

        return False

    for nei in neighbors:

        x_nei = (x[0] + nei[0], x[1] + nei[1])

        if is_in_region(x_nei) and d[x_nei[1] ][x_nei[0] ] < 0:

            return True

    return False
def next():

    min_d = 10 ** 9

    min_x = (-1, 0)

    for i in range(M):

        for j in range(N):

            x = (i, j)

            if is_interface(x):

                if d[x[1] ][x[0] ] < min_d:

                    min_x = x

                    min_d = d[x[1] ][x[0] ]

    return min_x
def calc_min_d(x):

    for nei in neighbors:

        x_nei = (x[0] + nei[0], x[1] + nei[1])

        if is_in_region(x_nei) and d[x_nei[1] ][x_nei[0] ] < 0:

            d[x_nei[1] ][x_nei[0] ] = val(x_nei) + d[x[1] ][x[0] ]
file = open("matrix.txt")

a = map(lambda s: map(int, s.split(',')), file.readlines())

file.close()
N = len(a)

M = len(a[0])

d = [ [ -1 ] * M for e in a ]
d[0][0] = a[0][0]

while True:

    x = next()

    if x[0] == -1:

        break

    calc_min_d(x)

print d