PROBLEM STATEMENT
You are given a rectangular board where each cell contains either an integer between 1 and 9,
inclusive, or a hole.
Place a token into the cell in the upper left corner of the board.
Now you can play a simple game. The game consists of moves, and each move
looks as follows:
Look at the number X written in the cell where your token is placed.
Choose one of the four basic directions (up, down, left, or right).
Move your token exactly X cells in the chosen direction. You can jump over all intermediate holes
in the path.
The game ends after a move that lands the token in a hole or outside the board.
Your goal is to make as many moves as possible.
The board is given as a vector board.
Characters '1' to '9' represent cells containing the corresponding integer, and
letters 'H' represent holes.
The upper left corner of the
board corresponds to the first character of the first element of board.
Write a method that will compute the maximum number of moves you can make on the
given board. If it is possible to make an arbitrarily large number of moves,
your method should return -1.
DEFINITION
Class:JumpingBoard
Method:maxJumps
Parameters:vector
Returns:int
Method signature:int maxJumps(vector board)
CONSTRAINTS
-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain between 1 and 50 characters, inclusive.
-All elements of board will be of the same length.
-Each element of board will only contain characters from the string "123456789H" (quotes for
clarity).
-The first character of the first element of board will not be 'H'.
EXAMPLES
0)
{"3942178",
"1234567",
"9123532"}
Returns: 5
In the first move you have to move the token to the right. In the second move you
have three choices. Moves to the left and to the right would bring you to cells
with a 9 and a 7, respectively, forcing you to end the game in the third move.
The optimal strategy is to make the second move down, the third one to the right,
and the fourth one up or to the left. In the last fifth move you are forced to leave
the board.
1)
{"2H3HH4HHH5"}
Returns: 4
Remember that you are allowed to jump over holes. Only landing in a hole is bad.
2)
{"3994",
"9999",
"9999",
"2924"}
Returns: -1
Make the first move down, and then you can jump left and right as many times as you wish.
3)
{"123456",
"234567",
"345678",
"456789"}
Returns: 4
On this board, all moves that don't end the game lead to the right or down.
In the best solution, the first three moves are: right, down, right.
4)
{"9"}
Returns: 1
There is no real choice here. The game will always end after the first move.
5)
{"2H9HH11",
"HHHHH11",
"9HHHH11"}
Returns: 2
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.