# Solutions for Problem 81

Given an 80x80 matrix, find the lowest cost path moving only right and down from the top left to bottom right corner.

## C by SanguineV

Runtime: negligible.

```#include <stdio.h>

// Declare the matrix as a two dimensional array.
unsigned long matrix = { {...} };

int main () {
// Iterators for the two dimesions.
int i,j;
// The edges have only a single path, so calculate those immediately.
i = 78;
while (i >= 0) {
matrix[i] += matrix[i+1];
matrix[i] += matrix[i+1];
i--;
}
// For each node, the path is its cost plus the lesser of the right or down step
// so iterate through the matrix and update all the node costs.
i = 78;
while (i >= 0) {
j = 78;
while (j >= 0) {
if(matrix[i+1][j] < matrix[i][j+1]) {
matrix[i][j] += matrix[i+1][j];
}
else {
matrix[i][j] += matrix[i][j+1];
}
j--;
}
i--;
}
// Cheapest cost is now the top left cost, so print it.
printf("Minimum path costs:%u\n",matrix);
return 0;
}
```

Same technique as used for problem 15 solutions, only now we have to have a local cost as well so need to work from the bottom right in reverse (or reverse all the matrix values, which is too much effort).

## Python by Althalus

Runtime: 11ms

```data = [....data here....]
#Let's deal with the edges seperate from the rest. Else we have to worry about handling out of bound errors
for i in range(78,-1,-1):
data[i] += data[i+1]
data[i] += data[i+1]

#For each cell, add which ever is lower, the cell to the right, or the cell below
for i in range(78,-1,-1):
for j in range(78,-1,-1):
data[i][j] += data[i][j+1] if (data[i][j+1] < data[i+1][j]) else data[i+1][j]

print data
#print data
print time() - start
```