@rahul: I got my fault. I didn't thought about that test case. I am thinking about applying DFS traversal algorithm for graph here. It may work here.
On Wed, Oct 17, 2012 at 9:01 AM, Rahul Kumar Patle < patlerahulku...@gmail.com> wrote: > @navin: still i am not getting your solution.. can you make more clear it > pls.. > > here is my doubt.. > > take input matrix and one temp visited matrix which stores the visited > path. > eg: > 1 1 0 0 0 > 1 1 0 0 0 > 0 1 1 1 0 > 0 1 1 1 0 > 0 0 1 1 1 > > Suppose i want to find the number of paths between M[4][2] -> M[0][0] > First i explore path M[4][2]->M[4][3]->M[3][3] and so on... your program > set 1 on visited matrix... on corresponding V[i][j] entries > next time i explore the path M[4][2]->M[3][2]->M[3][3]... but here we > found that V[3][3]=1 so we can't take this in put path... but actually both > are different paths.. > how you will ensure this. because we are maintaining only one visited > matrix. > > > > > > > On Wed, Oct 17, 2012 at 7:54 AM, Navin Kumar <algorithm.i...@gmail.com>wrote: > >> @Rahul: Loop won't occur because when you are visiting any matrix element >> then you are marking 1 in visited matrix. So second time it will be seen as >> a already visited element and it will choose another element (or path if >> exist) or will blocked. >> >> On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle < >> patlerahulku...@gmail.com> wrote: >> >>> @atul: in your solution object only can move down or right direction. but >>> in my problem object is free to move in any direction and hence there >>> are chances of cycle.. how to memoize cycle. >>> if there is cycle then your approach will give infinite solution. >>> >>> consider this maze >>> 1 1 0 0 0 >>> 1 1 0 0 0 >>> 0 1 1 0 0 >>> 0 1 1 0 0 >>> 0 0 1 1 1 >>> >>> you can see that object can take path >>> M[0][0] -> M[0][1] -> M[1][1]-> M[1][2]-> M[][]-> M[][] >>> OR >>> M[0][0] -> M[1][0] -> M[1][1]-> M[1][2]-> M[][]-> M[][] >>> But simple approach will also take path >>> M[0][0] -> M[0][1] -> M[1][1]-> M[1][0]-> M[0][0]-> M[0][1] ------ >>> CYCLE >>> >>> how you will avoid these cycles... >>> >>> On Tue, Oct 16, 2012 at 8:58 AM, atul anand <atul.87fri...@gmail.com>wrote: >>> >>>> http://www.geeksforgeeks.org/archives/13376 >>>> >>>> >>>> On Tue, Oct 16, 2012 at 8:56 AM, atul anand <atul.87fri...@gmail.com>wrote: >>>> >>>>> can be done simply by backtracking . >>>>> >>>>> On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle < >>>>> patlerahulku...@gmail.com> wrote: >>>>> >>>>>> Pls help to solve this que.. does any one have DP solution for following >>>>>> que. >>>>>> >>>>>> http://www.geeksforgeeks.org/archives/24488 >>>>>> section 5/question 2 >>>>>> >>>>>> Write a program to find all the possible paths from a starting point >>>>>> to dest point in a maze(2-D array). >>>>>> >>>>>> ex: 1 0 1 0 >>>>>> 1 1 1 1 >>>>>> 0 1 0 1 >>>>>> 0 0 1 1 >>>>>> >>>>>> If there is a block it’s represented by 0. >>>>>> If there is a path it’s represented by 1. >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Thanks and Regards: >>>>>> Rahul Kumar Patle >>>>>> M.Tech, School of Information Technology >>>>>> Indian Institute of Technology, Kharagpur-721302, >>>>>> India<http://www.iitkgp.ac.in/> >>>>>> Mobile No: +91-8798049298, +91-9424738542 >>>>>> Alternate Email: rahulkumarpa...@hotmail.com >>>>>> [image: >>>>>> Linkedin]<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> >>>>>> [image: Twitter] <https://twitter.com/rahulkumarpatle> >>>>>> <https://www.facebook.com/rkpatle> >>>>>> >>>>>> -- >>>>>> 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 >>>>>> algogeeks+unsubscr...@googlegroups.com. >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>> >>>>> >>>>> >>>> -- >>>> 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 >>>> algogeeks+unsubscr...@googlegroups.com. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Thanks and Regards: >>> Rahul Kumar Patle >>> M.Tech, School of Information Technology >>> Indian Institute of Technology, Kharagpur-721302, >>> India<http://www.iitkgp.ac.in/> >>> Mobile No: +91-8798049298, +91-9424738542 >>> Alternate Email: rahulkumarpa...@hotmail.com >>> [image: >>> Linkedin]<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> >>> [image: Twitter] <https://twitter.com/rahulkumarpatle> >>> <https://www.facebook.com/rkpatle> >>> >>> -- >>> 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 >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> 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 >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks and Regards: > Rahul Kumar Patle > M.Tech, School of Information Technology > Indian Institute of Technology, Kharagpur-721302, > India<http://www.iitkgp.ac.in/> > Mobile No: +91-8798049298, +91-9424738542 > Alternate Email: rahulkumarpa...@hotmail.com > [image: > Linkedin]<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> > [image: Twitter] <https://twitter.com/rahulkumarpatle> > <https://www.facebook.com/rkpatle> > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
