@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 < [email protected]> 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 <[email protected]>wrote: > >> http://www.geeksforgeeks.org/archives/13376 >> >> >> On Tue, Oct 16, 2012 at 8:56 AM, atul anand <[email protected]>wrote: >> >>> can be done simply by backtracking . >>> >>> On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle < >>> [email protected]> 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: [email protected] >>>> [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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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: [email protected] > [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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
