@Chi Have a look of http://www.codechef.com/SNACKTST/problems/KNIGHT1/ I have it solved with the approach what i already mentioned. For Breadth First Search and its application please refer http://en.wikipedia.org/wiki/Breadth-first_search
Great Minds Discuss Ideas Average Minds Discuss Events Small Minds Discuss People Shrish Chandra Mishra CSE Mnnit,Allahabad On Wed, Aug 25, 2010 at 6:14 PM, Chi <c...@linuxdna.com> wrote: > A spacefilling curve is also known as a quadtree-representation of a > plane. It's subdivide a plane in continuous 4 cells. My linear > implementations gives at each step one leaf. What do you mean with > unweigthed und BFS (Breadth-First-Search, perhaps?). How can you add 8 > vertices to the queue? It makes only sense to add 4 to queue with a > recursive approach!? A chessboard can be viewed as a graph of 2^n - > (n-1) edges. Sorry, I don't know the solution. > > On Aug 25, 6:11 am, SHRISH MISHRA <shrishkr...@gmail.com> wrote: > > The question is asking for a shortest path of some sort. If we consider > each > > cell as a vertex, then the edges will be the possible knight moves. For > > example, the cell (2,3) would have an edge to (and from) the cell (4,4), > > assuming that there are no pieces occupying either cell. This graph is > > unweighted, so the most natural algorithm to use is BFS. Having realized > > this, the graph itself is not necessary anymore; we can just use the > board > > directly. S is the source, and is the first cell/vertex added to the BFS > > queue. At each step, at most 8 more vertices will be added to the queue. > BFS > > will stop when T is found or when the queue is empty (no path to T was > > found). > > > > Great Minds Discuss Ideas > > Average Minds Discuss Events > > Small Minds Discuss People > > Shrish Chandra Mishra > > CSE NIT,Allahabad > > > > > > > > On Wed, Aug 25, 2010 at 8:25 AM, Chi <c...@linuxdna.com> wrote: > > > This is a spacefilling-curve. Optimal solution is a Hilbert-Curve or a > > > Morton-Curve. I have written one: > > >http://sourceforge.net/projects/hilbert-curve/files. > > > > > On Aug 25, 4:27 am, Algo geek <raja....@gmail.com> wrote: > > > > find the minimum no of moves by which a KNIGHT reaches the > destination > > > > from source in a 8x8 chess borad... > > > > > > **you will be given the starting position and ending position .. > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group.> To post to this group, send email > toalgoge...@googlegroups.com. > > > To unsubscribe from this group, send email to> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
