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.
KnightL on a Chessboard
KnightL on a Chessboard
Sort by
recency
|
121 Discussions
|
Please Login in order to post a comment
Python 3
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.