Path Sum: Three Ways

This is the same matrix as problem 81.

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

We can reuse our solution from problem 81 as well, with some slight modifications.

1. Instead of our queue initially containing only the top-left entry of the matrix, it will initially hold all the entries from the first column.
2. Additionally, instead of checking if we've reached the bottom-right entry, we'll stop on reaching any entry in the last column.
3. Finally, when adding new entries to the queue, we'll add the entry above our current entry, along with the entries to the right and below, as before.

import heapq

def minimal_path_sum(mat):
    m, n = mat.dimensions()
    
    destinations = {(i, n - 1) for i in range(0, m)}
    visited = set()
    queue = [(0, (i, 0)) for i in range(0, m)]
    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) in destinations:
            break
        
        if i - 1 >= 0:
            heapq.heappush(queue, (cost, (i - 1, j)))
            
        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)

260324

Copyright (C) 2025 filifa

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