[algogeeks] Re: a chessboard type problem
On May 4, 11:16 pm, max <[EMAIL PROTECTED]> wrote: > Say you have an n*n "chessboard" where each square is associated with > a real number (pos or neg). You want to navigate from one side to the > other by either moving one space ahead or one space ahead and one > space to the side (either side). I need an relatively efficient > algorithm that will optimize the path so that the sum of the values of > the squares that are touched is maximized. An easy to implement > algorithm would be great. > > Thanks in advance. > Max This looks like a dynamic programming problem. For each cell, where row=j and col=i, the only possible ways of reaching it are from (i-1,j-1), (i-1,j) and (i,j+1). Thus the maximum value of reaching that cell is value[i][j], if i == 0 value_of(i,j) =value[i][j] + max( value_of( i-1, j-1), value_of( i-1, j), value_of( i-1, j+1), otherwise Now you can determine the maximum possible value to reach each cell, and the highest valued cell to be reached in the last coloumn is the answer. Hope this helps. Muntasir --~--~-~--~~~---~--~~ 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.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: a chessboard type problem
It's just like Dyanamic programming graph problem ...u can apply dijkstra's shortest path..only thing u have more constraints to look out.. On 5/4/07, max <[EMAIL PROTECTED]> wrote: > > > Say you have an n*n "chessboard" where each square is associated with > a real number (pos or neg). You want to navigate from one side to the > other by either moving one space ahead or one space ahead and one > space to the side (either side). I need an relatively efficient > algorithm that will optimize the path so that the sum of the values of > the squares that are touched is maximized. An easy to implement > algorithm would be great. > > Thanks in advance. > Max > > > > > -- *** 30 years from now it doesn't matter which shoe you wore,which branded jean you wore..what all matters is WHAT YOU HAVE LEARNED AND HOW YOU HAVE USED IT. http://students.iiit.ac.in/~koushik_c --~--~-~--~~~---~--~~ 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.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] a chessboard type problem
Say you have an n*n "chessboard" where each square is associated with a real number (pos or neg). You want to navigate from one side to the other by either moving one space ahead or one space ahead and one space to the side (either side). I need an relatively efficient algorithm that will optimize the path so that the sum of the values of the squares that are touched is maximized. An easy to implement algorithm would be great. Thanks in advance. Max --~--~-~--~~~---~--~~ 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.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the original array
Assuming that 'n' is passed along the function
Pseudocode 1: O(n*n)
construct_array (int *a, int n, int *output)
{
construct_linkedlist(1 ... n);
Node *current = list->head;
int i=0, j=0;
int tvar;
for(i=0;ihead->data;
delete_head(llist);
} else {
for(tvar=a[i];tvar>1;tvar--)
current = current->next;
output[j++] = current->next->data;
remove_next(llist, current);
}
current = list->head;
}
}
Pseudocode 2: O(n*n)
construct_array(int *a, int n, int *output)
{
int i = 0, j = 0;
int op = 1;
while(op <= n) {
while(a[i++])
;
output[i] = op;
a[i] = -1;
for(j=0;j wrote:
>
>
> You are given an array of n numbers and each element is equal to the
> count of numbers less than that number in right hand side of the
> original and we have to find the original array;
> It is given that the n-numbers in the original array is from 1 to n.
>
> For ex. if the original array is 4,1,3,2
> Then we would we given the array 3,0,1,0
> Ex no 2. Original array 2,3,1,4
> Given array 1,1,0,0
> Ex no. 3 original array 5, 2,1,3,4
> Given array 4, 1,0,0,0
>
> Can any one suggest space and time efficient solution for this.
>
>
> >
>
--~--~-~--~~~---~--~~
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.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] G-String video http://www.teenwag.com/playvideo/1869
G-String video http://www.teenwag.com/playvideo/1869 --~--~-~--~~~---~--~~ 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.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Find the original array
You are given an array of n numbers and each element is equal to the count of numbers less than that number in right hand side of the original and we have to find the original array; It is given that the n-numbers in the original array is from 1 to n. For ex. if the original array is 4,1,3,2 Then we would we given the array 3,0,1,0 Ex no 2. Original array 2,3,1,4 Given array 1,1,0,0 Ex no. 3 original array 5, 2,1,3,4 Given array 4, 1,0,0,0 Can any one suggest space and time efficient solution for this. --~--~-~--~~~---~--~~ 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.google.com/group/algogeeks -~--~~~~--~~--~--~---
