import copy
from tools import load_data_table_integers
# from urllib.request import urlopen


def run(matrix=None):
    if matrix is None:
        matrix = load_data_table_integers(83, ',')

    # Alternative
    # file_url = 'https://projecteuler.net/project/resources/p082_matrix.txt'
    # matrix = list(map(lambda s: list(map(int, s[0].split(','))), (line.decode('UTF-8').split() for line in urlopen(file_url))))

    def print_matrix(m):
        for x in m:
            print ', '.join(['%3s' % i for i in x])
        print

    l = len(matrix)

    dp = [[float('inf') for x in range(l)] for y in range(l)]
    dp[0][0] = matrix[0][0]
    unstable, it = True, 0

    while unstable:
        unstable, it = False, it + 1

        for y in range(l):
            for x in range(l):
                min_neighbour = min(
                    dp[x-1][y] if x > 0 else float('inf'),
                    dp[x+1][y] if x + 1 < l else float('inf'),
                    dp[x][y-1] if y > 0 else float('inf'),
                    dp[x][y+1] if y + 1 < l else float('inf'),
                )

                tmp = min_neighbour + matrix[x][y]
                if tmp < dp[x][y]:
                    unstable = True
                    dp[x][y] = tmp

    return dp[-1][-1]
    

def test():
    m = [
        [131, 673, 234, 103, 18],
        [201, 96, 342, 965, 150],
        [630, 803, 746, 422, 111],
        [537, 699, 497, 121, 956],
        [805, 732, 524, 37, 331],
    ]
    assert run(m) == 2297   


if __name__ == '__main__':
    test()