Loading...
Loading...
Loading...
The college chess club has a puzzle board of r rows and c columns. A K is the square where a knight stands, T is the target square, # is a blocked square and . is free.
A knight moves in an L shape: two squares in one direction (up, down, left or right) and then one square to the side. It jumps, so the squares in between do not matter. It can land only on a square that is inside the board and not blocked. K and T are free squares.
Print the fewest moves the knight needs to reach T. If it can never get there, print −1.
K, T, # or ..K, T, # or ..K and exactly one T.Example 1
Input
3 3 K.. ... ..T
Output
4
Counting rows and columns from 1, one shortest route is (1, 1) → (2, 3) → (3, 1) → (1, 2) → (3, 3).
Example 2
Input
3 3 K.. .T. ...
Output
-1
On a 3 × 3 board no knight move ever lands on the centre square.
Try the problem first. Open one hint at a time.
Treat each square as a place and each knight move as a step. You want the fewest steps.
A queue that handles squares in order of distance works here just as it does in a maze, with 8 moves instead of 4.
There are 8 moves: change the row by 1 and the column by 2, or the row by 2 and the column by 1, with every mix of plus and minus signs.
Check the landing square only: it must be inside the board, not #, and not visited yet.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor