Sunday 2 November 2014

PROJECT EULER SOLUTION # 81

PROJECT EULER PROBLEM # 81
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.
131
673
234
103
18
201
96
342
965
150
630
803
746
422
111
537
699
497
121
956
805
732
524
37
331
Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

PROJECT EULER SOLUTION # 81
#include<stdio.h>
int main()
{
    int mat[80][80],minimum[80][80],i,j,n;
    char temp;
    FILE *f;
    n=80;
    f=fopen("matrix.txt","r");
    if(f)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n-1;j++)
                fscanf(f," %d%c",&mat[i][j],&temp);
            fscanf(f,"%d",&mat[i][j]);
        }
        minimum[0][0]=mat[0][0];
        for(j=1;j<n;j++)
            minimum[0][j]=minimum[0][j-1]+mat[0][j];
        for(i=1;i<n;i++)
            minimum[i][0]=minimum[i-1][0]+mat[i][0];
        for(i=1;i<n;i++)
            for(j=1;j<n;j++)
                minimum[i][j]=(minimum[i][j-1]>minimum[i-1][j]?minimum[i-1][j]:minimum[i][j-1])+mat[i][j];
        printf("answer = %d\n",minimum[n-1][n-1]);
    }
    else
        printf("there is some error in opening the file\n");
    return 0;
}


No comments:

Post a Comment