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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 > > [email protected]. > > To unsubscribe from this group, send email > > to>[email protected]<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 [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.
