TopCoder problem "JumpingBoard" used in SRM 368 (Division I Level One , Division II Level Three)



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 String[] 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:String[]
Returns:int
Method signature:int maxJumps(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.
-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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8245

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10936&pm=8245

Writer:

misof

Testers:

PabloGilberto , vorthys , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Recursion, Search