@Shrish: A chessboard can be viewed as a graph of 2^n - (n-1) edges is not correct, it must be n^2-(n-1) edges. By unweighted you mean, it has no payload, or cost-function, or probability. So you use a BFS, I guess I have to do it myself, because on the website I can't see a solution (neither I know your nickname). At least can you confirm me this number n^2-(n-1) edges if the knight start-position and end-position is such that he travels all points of the graph?
On Aug 25, 4:08 pm, SHRISH MISHRA <[email protected]> wrote: > @Chi > Have a look ofhttp://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 > referhttp://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 <[email protected]> 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 <[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%[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]<algogeeks%[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.
