// Solution to Project Euler problem 82

// left column to right column min path

#include <stdio.h>

#define MIN(a,b) (a>b?b:a)

int mat[80][80];

int cache[80][80];

main() {

    FILE *matrix;

    int i, j;

    matrix = fopen("matrix.txt", "r");

    for (i=0; i<80; i++) {

        for (j=0; j<80; j++) {

            fscanf(matrix, "%d,", mat[i]+j);

            cache[i][j] = 0;

        }

    }

    fclose(matrix);

    cache[79][79] = mat[79][79];

    printf("Solution: %d\n", minpath(0,0));

}

int minpath(int x, int y) {

    if (cache[x][y]) {

        return cache[x][y];

    }

    if (x == 79) {

        cache[x][y] = mat[x][y] + minpath(x, y+1);

        return cache[x][y];

    } else if (y == 79) {

        cache[x][y] = mat[x][y] + minpath(x+1, y);

        return cache[x][y];

    } else {

        int temp1 = minpath(x+1,y);

        int temp2 = minpath(x,y+1);

        cache[x][y] = mat[x][y] + MIN(temp1,temp2);

        return cache[x][y];

    }

}