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 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.
