## NOTE: This problem is a significantly more challenging version of Problem 81.

In the $5$ by $5$ matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to $2297$.

$$

\begin{pmatrix}

\color{red}{131} & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\

\color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & \color{red}{150}\\

630 & 803 & 746 & \color{red}{422} & \color{red}{111}\\

537 & 699 & 497 & \color{red}{121} & 956\\

805 & 732 & 524 & \color{red}{37} & \color{red}{331}

\end{pmatrix}

$$

Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing an $80$ by $80$ matrix.

### To solve this problem, we need to find the minimal path sum from the top left to the bottom right in a given matrix, just like in the example provided. We can use a dynamic programming approach to solve this problem efficiently.

Here is a step-by-step solution using Python programming:

1. Read the matrix from the provided text file. We’ll assume the file is named “matrix.txt”. The matrix will be stored as a 2D list.

“`python

def read_matrix(file_name):

matrix = []

with open(file_name, ‘r’) as file:

for line in file:

row = list(map(int, line.strip().split(‘,’))) # assuming each element is separated by a comma

matrix.append(row)

return matrix

matrix = read_matrix(“matrix.txt”)

“`

2. Initialize a new 2D list, `dp`, with the same dimensions as the matrix. `dp[i][j]` will represent the minimal path sum to reach the cell at position `(i,j)` from the top left corner.

“`python

dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]

dp[0][0] = matrix[0][0] # the top-left cell has the same minimal path sum as its value

“`

3. Calculate the minimal path sum for each cell in the matrix.

“`python

# Calculate minimal path sum for the first row (moving only right)

for j in range(1, len(matrix[0])):

dp[0][j] = dp[0][j-1] + matrix[0][j]

# Calculate minimal path sum for the first column (moving only down)

for i in range(1, len(matrix)):

dp[i][0] = dp[i-1][0] + matrix[i][0]

# Calculate minimal path sum for the remaining cells

for i in range(1, len(matrix)):

for j in range(1, len(matrix[0])):

# Choose the minimum path sum from either coming from the left or from above

dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + matrix[i][j]

“`

4. The minimal path sum from the top left to the bottom right will be stored in `dp[-1][-1]`.

“`python

minimal_path_sum = dp[-1][-1]

print(“The minimal path sum is:”, minimal_path_sum)

“`

Putting it all together, here is the complete Python code to solve the problem:

“`python

def read_matrix(file_name):

matrix = []

with open(file_name, ‘r’) as file:

for line in file:

row = list(map(int, line.strip().split(‘,’))) # assuming each element is separated by a comma

matrix.append(row)

return matrix

matrix = read_matrix(“matrix.txt”)

dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]

dp[0][0] = matrix[0][0]

for j in range(1, len(matrix[0])):

dp[0][j] = dp[0][j-1] + matrix[0][j]

for i in range(1, len(matrix)):

dp[i][0] = dp[i-1][0] + matrix[i][0]

for i in range(1, len(matrix)):

for j in range(1, len(matrix[0])):

dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + matrix[i][j]

minimal_path_sum = dp[-1][-1]

print(“The minimal path sum is:”, minimal_path_sum)

“`

By running this code, you will get the minimal path sum from the top left to the bottom right of the provided matrix.

##### More Answers:

Square Root Digital ExpansionPath Sum: Two Ways

Path Sum: Three Ways