@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 k
@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
Sm
In case of DP also, you will require to move in a BFS manner only, a neatly
written BFS will definitely make it fast.
On Wed, Aug 25, 2010 at 7:34 PM, krazee koder wrote:
> i think v can solve it by DP technique..similar to LCS prob or
> assembly line scheduling(Cormen et. al.)
>
> consider a two
i think v can solve it by DP technique..similar to LCS prob or
assembly line scheduling(Cormen et. al.)
consider a two dimensional look up table. Each index refers to
shortest distance taken by the knight to move that square.
recursively try to call a fn. that changes source to the current
square
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 mak
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
unweig
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 wrote:
> find the minimum no of moves by which a KNIGHT reaches the destination
> from source in a 8x8 chess