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.
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.

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.

min_s(M[m,n])=min(min_s(M[m,n1]),min_s(M[m1,n]))
ReplyDelete+M[m,n]
@Anonymous .. ur solution is correct for the first part of the problem.
ReplyDelete#include
ReplyDelete#include
#include
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(a1); k >= (b); k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define REPD(k,a) for(int k=a1; 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][i1] ;
FOR(j,1,n)
a[j][0] += a[j1][0] ;
FOR(i,1,n)
FOR(j,1,n){
a[i][j] += min (a[i1][j],a[i][j1]) ;
}
printf("%d\n",a[n1][n1]);
}
return 0;
}
This is the solution to the first problem.
@Spectator ... correct !!!
ReplyDeleteThis can be solved using Dijkstra
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteBelow 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.
ReplyDeleteprivate 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;
}