//atul anand code :-
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define size 5

int minA(int a , int b)
{

return a > b ? b : a;
}

int minB(int a,int b,int c)
{
	if( a < b && a < c)
		return a;
	if(b < a && b < c)
		return b;
	if(c < a && c < b)
		return c;
}
int EulerProblem82(int mat[][size])
{

int *sol=(int *)calloc(sizeof(int),size);
int i,j,minVal;

	for(i=0;i<size;i++)
	{
		sol[i]=mat[i][size - 1];
		
	}

	for(i=size-2;i>=0;i--)
	{
		j=0;
	        // checking if it is min to go right or go down and then right
		sol[j]=minA((mat[j][i]+mat[j+1][i]+sol[j+1]),sol[j]+mat[j][i]);	
		
		for(j=1;j<size-1;j++)
		{
			
				// checking if sol[j-1] has its minimum value by going right or go up and then right 
				if(sol[j-1]!=(mat[j][i]+mat[j-1][i]+sol[j]))
				{
					//checking if min min is to go right or up and then right or down and then right
					sol[j]=minB(sol[j-1]+mat[j][i], sol[j]+mat[j][i],(mat[j][i]+mat[j+1][i]+sol[j+1]));
				}
				else
				{
					//if sol[j-1] took min path by going down and then right..hence no need to check up condition for sol[j]
					sol[j]=minA(sol[j]+mat[j][i],(mat[j][i]+mat[j+1][i]+sol[j+1]));
				}
		
		}
				 //checking if it is min to go right or go up and then right
				sol[j]=minA(sol[j-1]+mat[j][i] , sol[j]+mat[j][i]);
	
	}
	
	minVal=INT_MAX;
	for(i=0;i<size;i++)
	{
		if(sol[i] < minVal)
		{
			minVal=sol[i];
		}
	}

return minVal;
}

int main()
{
int arr[][size]={{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}
                };


printf("Minimum path value = %d\n\n",EulerProblem82(arr));
return 0;
}