PROBLEM STATEMENT
Facebook engineers love playing chess. They also like to play other games on the chessboard.
Today, they were wondering how many cells a knight would visit on the chessboard if it followed
some predefined algorithm.
You are given a vector board describing a standard 8x8 chessboard, where the c-th
character of the r-th element corresponds to the cell in row r, column c. Some cells are blocked
and cannot be jumped into. These will be represented with a '*'. All other cells are marked with a
'.', except for the starting position of the knight, which is marked with a 'K'.
A valid jump for a knight consists of shifting one square along one axis and two squares along the
other axis. A cell is "accessible" if it is not blocked and it has not been visited by the knight
before. The starting position of the knight is considered to be visited, and each time the knight
jumps into a new cell, that cell becomes visited. The accessibility number of a cell is the
number of accessible cells that the knight can make a valid jump to from that cell. Note that
accessibility numbers of cells may change as the knight moves through the board and visits more
cells.
The knight will use the following simple algorithm to traverse the board. On each move, it will
make a valid jump into the accessible cell with the lowest accessibility number. In case of a
tie, it will choose the one with the lowest row number, and if there is still a tie, it will
choose the one among them with the lowest column number. The knight will stop moving when it can
no longer make a valid jump into an accessible cell.
Return the number of cells that the knight will visit (including the starting cell).
DEFINITION
Class:KnightsTour
Method:visitedPositions
Parameters:vector
Returns:int
Method signature:int visitedPositions(vector board)
CONSTRAINTS
-board will contain exactly 8 elements.
-Each element of board will contain exactly 8 characters '.', 'K' or '*'.
-Character 'K' will appear exactly once in board.
EXAMPLES
0)
{"........"
,".*.*...."
,".*......"
,"..K...*."
,"*...*..."
,"...*...."
,"...*.*.."
,"........"}
Returns: 39
From its starting cell K, the knight can jump to cells A, B and C, which have accessibility
numbers of 3, 6 and 4, respectively (see first image below). It will jump to cell A because it
has the lowest accessibility number.
From cell A, it can then jump to cells D, E and F, which have accessibility numbers of 1, 5 and 4,
respectively (see second image). It will choose cell D. It will continue in this fashion and
visit a total of 39 cells.
??
1)
{"K......."
,"........"
,"........"
,"........"
,"........"
,"........"
,"........"
,"........"}
Returns: 64
If no cells are blocked, then the knight will end up visiting every cell by following the given
algorithm.
2)
{"********"
,"*******."
,"********"
,"**.***.*"
,"********"
,"***.*.**"
,"********"
,"****K***"}
Returns: 3
From its starting cell K, the knight can jump to cells A and B, which have accessibility numbers
of 1 (see the image). Both A and B have the same accessibility number and the same row number, so
it will jump to A because it has the lowest column number. It will then jump to C and stop,
visiting a total of 3 cells.
??
3)
{"*.*....*"
,".......*"
,"**...*.."
,"..***..."
,".**.*..."
,"..*.*..K"
,"..***.*."
,"**...*.."}
Returns: 17
4)
{"..*...*."
,"**.....*"
,"*..*...."
,"*..*...."
,".....*.."
,"....*..K"
,"**.*...*"
,"..**...."}
Returns: 27
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)2010, TopCoder, Inc. All rights reserved.