# Euler Solution 81

### From ProgSoc Wiki

# 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[80][80] = { {...} }; 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][79] += matrix[i+1][79]; matrix[79][i] += matrix[79][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[0][0]); 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[79][i] += data[79][i+1] data[i][79] += data[i+1][79] #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[0][0] #print data print time() - start