We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For every position,the Knight has at most 8 directions to go.Therfore, all the positions form a graph that each vertex has at most 8 edges. If we want the Knight move from (0,0) to (n-1,n-1) within the minimum steps, we can use BFS(Breadth-First Search) to enumerate all possibilities. Before we use BFS, we can simplify the situations:
Especially, when a==b, we can be certain that the minimum steps that the Knight will take is to move along the diagonal. Thus, the next thing to do is to judge whether (n-1)%a==0 is valid or not. And the result of (n-1)/a is the answer for a==b.
Here is my C++ solution.
C++ solution of Knight on a Chessboard.
Thanks for @sumesh1999. I revised and optimized my code after referring to your code.
KnightL on a Chessboard
You are viewing a single comment's thread. Return to all comments →
For every position,the Knight has at most 8 directions to go.Therfore, all the positions form a graph that each vertex has at most 8 edges. If we want the Knight move from
(0,0)
to(n-1,n-1)
within the minimum steps, we can use BFS(Breadth-First Search) to enumerate all possibilities. Before we use BFS, we can simplify the situations: Especially, whena==b
, we can be certain that the minimum steps that the Knight will take is to move along the diagonal. Thus, the next thing to do is to judge whether(n-1)%a==0
is valid or not. And the result of(n-1)/a
is the answer fora==b
. Here is my C++ solution.