Hello,
first of all, thanks to all for help!
as Lego Haryanto alredy guessed, this one was taken from some on-line
competition site. The next problem of this kind is a similar matrix of
size 80*80 except that you can start in any column and finish in any
other column on the other side of the matrix (i,0 => i,N-1). You can
move up down or right.
Now, as I'm doing all this problems to get more programming skills, I
tried the technique Karthik Krishnamurthy suggested - Dynamic
programming.
I reversed the path rules (I defined them as going from right to left)
and I got to the conclusion that each element (if we left out the
N-1'th row) can be accessed from N different locations , (eg. for
element 5) :
123
456
789
5+6
5+8+9
5+2+3
Knowing this, I coded a simple snippet which doesn't work :
=================================
int main() {
int i,j,k,c,min,res = INT_MAX;
for (j = N-2; j>=0; j--) {
for (i = N-1;i>= 0; i--) {
min = matrix[i][j+1];
c = 0;
for (k = i - 1; k >= 0; k--) {
c += matrix[k][j];
if (c + matrix[k][j+1] < min)
min = c + matrix[k][j+1];
}
c = 0;
for (k = i+1; k < N; k++) {
c += matrix[k][j];
if (c + matrix[k][j+1] < min)
min = c + matrix[k][j+1];
}
matrix[i][j] += min;
if (j == 0 && res > matrix[i][j]) {
res = matrix[i][j];
}
}
}
return printf("%d\n", res);
}
=================================
I tried a recursive method as in the previous post and the answer was
the same as with this code, so the problem is definitely in the
algortihm, but I'm really to stupid to get the reason - anyone can help
me?
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
