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.
|