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.

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331



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.


13167323410318
20196342965150
630803746422111
537699497121956
80573252437331


8 comments :

  1. min_s(M[m,n])=min(min_s(M[m,n-1]),min_s(M[m-1,n]))
    +M[m,n]

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

    ReplyDelete
  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[50][50] ;

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

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

    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.

    ReplyDelete
  4. This can be solved using Dijkstra

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. This comment has been removed by the author.

    ReplyDelete
  7. 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();
    visitedNodes.add("" + i + j);
    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;
    visitedNodes.add("" + i + j);
    }

    System.out.println("route = " + route.toString());

    return minSum;
    }

    ReplyDelete