TravellingChessboard | Topcoder Archive

Problem Statement

You are maneuvering a chess knight on a chessboard, trying to get it from a given starting square to a given destination square. Some of the squares on the board are blocked and the knight can't enter them.

In one move the knight moves to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. A knight marked K below can move to any of the ? cells::

.?.?.
?...?
..K..
?...?
.?.?.

You are given a chessboard as String[] board. Each element of board represents one row of squares, and each character represents a square. 'S' and 'D' mark starting and destination squares, 'X' marks a blocked square and '.' marks an open square which can be entered by the knight.

Return the minimum number of moves required to move the knight from the starting square to the destination one, visiting only open squares. If it is impossible to move the knight as described, return -1.

Definition

Class:: TravellingChessboard
Method:: minimumMoves
Parameters:: String[]
Returns:: int
Method signature:: int minimumMoves(String[] board)
(be sure your method is public)

Constraints

board will contain between 1 and 50 elements, inclusive.
Each element of board will contain between 1 and 50 characters, inclusive.
Each element of board will be the same length.
Each character of each element of board will be one of 'S', 'D', 'X' or '.'.
Exactly one character in board will be 'S' and one will be 'D'.

Examples

```
{"S..",
 "..D"}
```
```
Returns: 1
```
It's a simple single move to get from the start to the destination.
```
{"..X..",
 "S...D",
 "..X..",
 "....."}
```
```
Returns: 4
```
You can't get to the destination in two moved because both squares required for that are blocked.. So, a longer path is needed: ..X.. 0.2.4 ..X.. .1.3.
```
{"..D",
 "...",
 "S.."}
```
```
Returns: 4
```
No cells that can't be used, but given the small size of the board, it takes quite a few moves to reach the end, one possible path looks like this: .14 3.. 0.2
```
{".X.X",
 "XS..",
 "..D.",
 "X..."}
```
```
Returns: -1
```
While the knight can at first make some moves, it can never reach the destination.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.