Thursday, February 2, 2012

Euler problem : Finding the minimum sum

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 This can be solved by an easy application of the DP.
A nice variation of the  above problem is to find the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297. 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 1. min_s(M[m,n])=min(min_s(M[m,n-1]),min_s(M[m-1,n]))
+M[m,n]

2. @Anonymous .. ur solution is correct for the first part of the problem.

3. #include
#include
#include
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(a-1); k >= (b); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define REPD(k,a) for(int k=a-1; k >-1; --k)
using namespace std ;

int main()
{
int n ;
int a ;

while(1){
scanf ( "%d" , &n ) ;
int i , j ;
REP(i,n)
REP(j,n)
scanf ( "%d" , &a[i][j] ) ;

FOR(i,1,n)
a[i] += a[i-1] ;
FOR(j,1,n)
a[j] += a[j-1] ;

FOR(i,1,n)
FOR(j,1,n){
a[i][j] += min (a[i-1][j],a[i][j-1]) ;
}

printf("%d\n",a[n-1][n-1]);
}

return 0;
}
This is the solution to the first problem.

4. @Spectator ... correct !!!

5. This can be solved using Dijkstra

6. This comment has been removed by the author.

7. This comment has been removed by the author.

8. Below is my solution. It starts from Position(4,4) and will back track till it reaches Position(0,0). This will also print the "Path" backwards.

private static int minSumVariation(int[][] grid) {
if (grid == null) {
throw new NullPointerException();
}
int i = 4;
int j = 4;
int minSum = grid[i][j];
Set visitedNodes = new HashSet();
StringBuilder route = new StringBuilder();
route.append("" + minSum);
while (true) {
if (i - 1 < 0 && j - 1 < 0) {
break;
}

int min = 0;
int iNext = 0;
int jNext = 0;

if (j - 1 >= 0) {
if (!visitedNodes.contains("" + i + (j - 1))) {
min = grid[i][j - 1];
iNext = i;
jNext = j - 1;
}
}
if (i - 1 >= 0) {
if (!visitedNodes.contains("" + (i - 1) + j)) {
if (min == 0) {
min = grid[i - 1][j];
iNext = i - 1;
jNext = j;
} else if (min > grid[i - 1][j]) {
min = grid[i - 1][j];
iNext = i - 1;
jNext = j;
}
}
}
if (i + 1 < 5) {
if (!visitedNodes.contains("" + (i + 1) + j)) {
if (min == 0) {
min = grid[i + 1][j];
iNext = i + 1;
jNext = j;
} else if (min > grid[i + 1][j]) {
min = grid[i + 1][j];
iNext = i + 1;
jNext = j;
}
}
}
if (j + 1 < 5) {
if (!visitedNodes.contains("" + i + (j + 1))) {
if (min == 0) {
min = grid[i][j + 1];
iNext = i;
jNext = j + 1;
} else if (min > grid[i][j + 1]) {
min = grid[i][j + 1];
iNext = i;
jNext = j + 1;
}
}
}
route.append(" - " + min);
minSum += min;
i = iNext;
j = jNext;