//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;
}
Ly9hdHVsIGFuYW5kIGNvZGUgOi0KI2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CiNpbmNsdWRlPGxpbWl0cy5oPgojZGVmaW5lIHNpemUgNQoKaW50IG1pbkEoaW50IGEgLCBpbnQgYikKewoKcmV0dXJuIGEgPiBiID8gYiA6IGE7Cn0KCmludCBtaW5CKGludCBhLGludCBiLGludCBjKQp7CglpZiggYSA8IGIgJiYgYSA8IGMpCgkJcmV0dXJuIGE7CglpZihiIDwgYSAmJiBiIDwgYykKCQlyZXR1cm4gYjsKCWlmKGMgPCBhICYmIGMgPCBiKQoJCXJldHVybiBjOwp9CmludCBFdWxlclByb2JsZW04MihpbnQgbWF0W11bc2l6ZV0pCnsKCmludCAqc29sPShpbnQgKiljYWxsb2Moc2l6ZW9mKGludCksc2l6ZSk7CmludCBpLGosbWluVmFsOwoKCWZvcihpPTA7aTxzaXplO2krKykKCXsKCQlzb2xbaV09bWF0W2ldW3NpemUgLSAxXTsKCQkKCX0KCglmb3IoaT1zaXplLTI7aT49MDtpLS0pCgl7CgkJaj0wOwoJICAgICAgICAvLyBjaGVja2luZyBpZiBpdCBpcyBtaW4gdG8gZ28gcmlnaHQgb3IgZ28gZG93biBhbmQgdGhlbiByaWdodAoJCXNvbFtqXT1taW5BKChtYXRbal1baV0rbWF0W2orMV1baV0rc29sW2orMV0pLHNvbFtqXSttYXRbal1baV0pOwkKCQkKCQlmb3Ioaj0xO2o8c2l6ZS0xO2orKykKCQl7CgkJCQoJCQkJLy8gY2hlY2tpbmcgaWYgc29sW2otMV0gaGFzIGl0cyBtaW5pbXVtIHZhbHVlIGJ5IGdvaW5nIHJpZ2h0IG9yIGdvIHVwIGFuZCB0aGVuIHJpZ2h0IAoJCQkJaWYoc29sW2otMV0hPShtYXRbal1baV0rbWF0W2otMV1baV0rc29sW2pdKSkKCQkJCXsKCQkJCQkvL2NoZWNraW5nIGlmIG1pbiBtaW4gaXMgdG8gZ28gcmlnaHQgb3IgdXAgYW5kIHRoZW4gcmlnaHQgb3IgZG93biBhbmQgdGhlbiByaWdodAoJCQkJCXNvbFtqXT1taW5CKHNvbFtqLTFdK21hdFtqXVtpXSwgc29sW2pdK21hdFtqXVtpXSwobWF0W2pdW2ldK21hdFtqKzFdW2ldK3NvbFtqKzFdKSk7CgkJCQl9CgkJCQllbHNlCgkJCQl7CgkJCQkJLy9pZiBzb2xbai0xXSB0b29rIG1pbiBwYXRoIGJ5IGdvaW5nIGRvd24gYW5kIHRoZW4gcmlnaHQuLmhlbmNlIG5vIG5lZWQgdG8gY2hlY2sgdXAgY29uZGl0aW9uIGZvciBzb2xbal0KCQkJCQlzb2xbal09bWluQShzb2xbal0rbWF0W2pdW2ldLChtYXRbal1baV0rbWF0W2orMV1baV0rc29sW2orMV0pKTsKCQkJCX0KCQkKCQl9CgkJCQkgLy9jaGVja2luZyBpZiBpdCBpcyBtaW4gdG8gZ28gcmlnaHQgb3IgZ28gdXAgYW5kIHRoZW4gcmlnaHQKCQkJCXNvbFtqXT1taW5BKHNvbFtqLTFdK21hdFtqXVtpXSAsIHNvbFtqXSttYXRbal1baV0pOwoJCgl9CgkKCW1pblZhbD1JTlRfTUFYOwoJZm9yKGk9MDtpPHNpemU7aSsrKQoJewoJCWlmKHNvbFtpXSA8IG1pblZhbCkKCQl7CgkJCW1pblZhbD1zb2xbaV07CgkJfQoJfQoKcmV0dXJuIG1pblZhbDsKfQoKaW50IG1haW4oKQp7CmludCBhcnJbXVtzaXplXT17ezEzMSw2NzMsMjM0LDEwMywxOH0sCiAgICAgICAgICAgICAgICAgezIwMSw5NiwzNDIsOTY1LDE1MH0sCiAgICAgICAgICAgICAgICAgezYzMCw4MDMsNzQ2LDQyMiwxMTF9LAogICAgICAgICAgICAgICAgIHs1MzcsNjk5LDQ5NywxMjEsOTU2fSwKICAgICAgICAgICAgICAgICB7ODA1LDczMiw1MjQsMzcsMzMxfQogICAgICAgICAgICAgICAgfTsKCgpwcmludGYoIk1pbmltdW0gcGF0aCB2YWx1ZSA9ICVkXG5cbiIsRXVsZXJQcm9ibGVtODIoYXJyKSk7CnJldHVybiAwOwp9