http://projecteuler.net/problem=83

83.py

# -*- coding: utf-8 -*-

class Int(int):

    def __eq__(self, other):
        if int(self) == -1 or int(other) == -1:
            return True
        return int(self) == int(other)

def main():
    matrix = [[int(i) for i in line.split(',')] for line in open("matrix.txt", 'r').read().split('\n')]
    width, height, minimum = len(matrix[0]), len(matrix), min([min(line) for line in matrix])
    opened, closed = [(Int(matrix[0][0] + minimum * ((width - 1) + (height - 1))), Int(matrix[0][0]), 0, 0)], []
    while (Int(-1), Int(-1), width - 1, height - 1) not in closed and len(opened) > 0:
        current = sorted(opened)[0]
        opened.remove(current)
        closed.append(current)
        for x0, y0 in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x, y = current[2] + x0, current[3] + y0
            if x >= 0 and x < width and y >= 0 and y < height and (Int(-1), Int(-1), x, y) not in closed:
                if (Int(-1), Int(-1), x, y) in opened and current[1] + matrix[y][x] < opened[opened.index((Int(-1), Int(-1), x, y))][1]:
                    opened.remove((Int(-1), Int(-1), x, y))
                    opened.append((Int(current[1] + matrix[y][x] + minimum * ((width - 1 - x) + (height - 1 - y))), Int(current[1] + matrix[y][x]), x, y))
                elif (Int(-1), Int(-1), x, y) not in opened:
                    opened.append((Int(current[1] + matrix[y][x] + minimum * ((width - 1 - x) + (height - 1 - y))), Int(current[1] + matrix[y][x]), x, y))
    print closed[closed.index((Int(-1), Int(-1), width - 1, height - 1))][1]

if __name__ == "__main__":
    main()