Path Sum: Four Ways

This is the same matrix as problem 81 and problem 82.

with open("txt/0083_matrix.txt") as f:
    mat = matrix((int(n) for n in line.split(',')) for line in f)

Once again, we can reuse our solution from problem 81, simply modifying so that when adding entries to the queue, we'll add all entries above, below, left, and right of our current entry.

import heapq

def minimal_path_sum(mat):
    m, n = mat.dimensions()
    
    visited = set()
    queue = [(0, (0, 0))]
    while queue != []:
        cost, (i, j) = heapq.heappop(queue)
        
        if (i, j) in visited:
            continue
        visited.add((i, j))
        
        cost += mat[i, j]
        
        if (i, j) == (m - 1, n - 1):
            break
            
        if i - 1 >= 0:
            heapq.heappush(queue, (cost, (i - 1, j)))
            
        if j - 1 >= 0:
            heapq.heappush(queue, (cost, (i, j - 1)))
        
        if i + 1 < m:
            heapq.heappush(queue, (cost, (i + 1, j)))
            
        if j + 1 < n:
            heapq.heappush(queue, (cost, (i, j + 1)))
            
    return cost

minimal_path_sum(mat)

425185

Copyright (C) 2025 filifa

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.