[algogeeks] Re: Find the number of paths between two points on a grid
missed the m*n in the last fnxn call in recursion area...PLZ CORRECT
No, it's definitely not going the right way..
i wonder if this can be done using that formula...
here's this algo i just thought.
Suppose u've gotm horizontal lines and n vertical and ugive each of them an index value. i.e. a 3x2 grid would be like...
___!_(1)_! (2)___
___!_(3)_! (4)___
___!_(5)_! (6)___
!!
we start from node x to node y and the nodes we have traversed are stored in an array named TRAVERSED..the fnxn uses recursion and the algo can be said as a backtracking algo since it checks all the nodes in a particular path if already travelled it returns from that very node
ways = 0 ; // initially
Start( x,y, TRAVERSED)
{
if(x is an element of TRAVERSED) // can be found using a loop
return;
store x in TRAVERSED
if(x==y)
{
ways++; // ways is the variable thatcounts the valid path found
return;
}
if (x-1=0) // moving left from current node
start(x-1,y,TRAVERSED);
if (x+1=m*n) // movingright from current node
start(x+1,y,TRAVERSED);
if (x-n=0) // movingup from current node
start(x-n,y,TRAVERSED);
if (x+n=m*n) // movingdown from current node
start(x+n,y,TRAVERSED);
}
-- Smile, it's the second best thing you can do with your lips..By the way...the First thing is ur KISS :-)Prashant Bhargava--
www.excogitation.tkor
www.hemantdesign.com/prashant -- Smile, it's the second best thing you can do with your lips..
By the way...the First thing is ur KISS :-)Prashant Bhargava-- www.excogitation.tkor www.hemantdesign.com/prashant
--~--~-~--~~~---~--~~
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 number of paths between two points on a grid
There's a small error in my formula. The formula holds for a NxM grid (N horizontal and M vertical lines) where N= n+1 and M = m+1, which essentially boils down to C(N+M-2, N-1) = C(N+M-2,M-1). This should work fine. -Shishir --~--~-~--~~~---~--~~ 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 number of paths between two points on a grid
Can't understand man!!! can u explain and also does your formula take into account the position of starting and ending points or is it just about the corner points that u r talking abt -- Smile, it's the second best thing you can do with your lips.. By the way...the First thing is ur KISS :-)Prashant Bhargava-- www.excogitation.tkor www.hemantdesign.com/prashant --~--~-~--~~~---~--~~ 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 number of paths between two points on a grid
This works only if you assume that you do not go backwards i.e. your max path length is N+M-2. If you can go backwards, then I think that there are more paths than just these. e.g. in 3x3 grid you can have path length more than 4 (1,1) - (1,2) - (2,2) - (2,1) - (3,1) - (3,2) - (3,3) I havent given much thought on how to count all possible paths ... maybe some variation of Floyd-Warshalls ... -Dhyanesh On 4/6/06, shishir [EMAIL PROTECTED] wrote: There's a small error in my formula. The formula holds for a NxM grid (N horizontal and M vertical lines) where N= n+1 and M = m+1, which essentially boils down to C(N+M-2, N-1) = C(N+M-2,M-1). This should work fine. -Shishir --~--~-~--~~~---~--~~ 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 number of paths between two points on a grid
Well the formula works only for the corner end points as starting and ending node and that too on the diagonal ends. Its not a general formula for any set of starting/ending nodes. @Dhyanesh I think the problem clearly states that the nodes can only be traversed once i.e. no repetition. --~--~-~--~~~---~--~~ 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] Driving directions algorithm
I'm looking for an algorithm which achieves the following: Given a directed, unweighted graph G and nodes g[i] and g[j] in G, find the shortest path from g[i] to g[j]. Use a single breadth-first traversal of G, marking visited nodes as you go. This is essentially a tree traversal problem. The trick is to end up with an ordered list of nodes representing the path (i.e. traverse to g13, then to g42, then to ...) like you would after completing a depth-first search, even though you're actually doing a breadth-first search. Is this a well-known problem? I imagine it can be solved using an auxiliary list to keep track of parents, but so far I haven't hit upon the right combination of stack and queue operations to do the job. Btw. this is something I'm curious about and want for my pet programming language (not a homework assigment). --~--~-~--~~~---~--~~ 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: Problem
Hi, 0 x y z N-1 is the requirement. Lei --~--~-~--~~~---~--~~ 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] Links on the Benefits of Vegetarianism
Watch Meet Your Meat from People for the Ethical Treatment of Animals (PETA): http://www.petatv.com/tvpopup/Prefs.asp?video=meet_your_meat 101 Reasons to be vegetarian: http://www.vivavegie.org/vv101/index.html Famous vegetarian athletes (list compiled by the International Vegetarian Union): http://www.ivu.org/people/sports/index.html __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com --~--~-~--~~~---~--~~ 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] can you find this
I need two algorithms to multiplicat two matrix in C++ and thank you so much Love cheap thrills? Enjoy PC-to-Phone calls to 30+ countries for just 2ยข/min with Yahoo! Messenger with Voice. --~--~-~--~~~---~--~~ 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 number of paths between two points on a grid
Shishir , have a look at my example ... there is no repetition of points in it. Your formula wont work for it. -Dhyanesh On 4/6/06, shishir [EMAIL PROTECTED] wrote: Well the formula works only for the corner end points as starting and ending node and that too on the diagonal ends. Its not a general formula for any set of starting/ending nodes. @Dhyanesh I think the problem clearly states that the nodes can only be traversed once i.e. no repetition. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
