JumpingGame | Topcoder Archive

Problem Statement

You are playing a game with a number of small pegs. In the game, the pegs are located on a 6x6 board. The board will be given to you as a String[], board, each of whose elements represents one row of the board. A 'P' represents a peg, and a '.' represents an empty space. During a turn, you may either move a peg to a horizontally or vertically adjacent empty space, or you may jump a peg over a single horizontally or vertically adjacent peg into the next space, which must be empty. When a peg is jumped over, that peg is removed, creating an empty space. The board does not wrap around, and you cannot move or jump outside of the board. The goal is to remove all the pegs but one, and have that peg in row goal[0], column goal[1] (both indexed from 0).

Your task is to determine the fewest moves required to transform the board from its current state to the goal state. Your friend claims the board can be transformed in limit moves, and you are trying to verify this claim. If the board can be transformed in limit or fewer moves, return the minimum number of moves required, otherwise return -1.

Definition

Class:: JumpingGame
Method:: fewestMoves
Parameters:: String[], int[], int
Returns:: int
Method signature:: int fewestMoves(String[] board, int[] goal, int limit)
(be sure your method is public)

Constraints

board will contain exactly 6 elements, each with exactly 6 characters.
Each character in board will be 'P' or '.'.
limit will be between 1 and 12, inclusive.
goal will contain exactly 2 elements, each between 0 and 5, inclusive.
There will be at least one 'P' in board.

Examples

```
{"......",
 "......",
 "......",
 "......",
 "......",
 "...PPP"}
```
```
{5,5}
```
```
5
```
```
Returns: 4
```
Considering only the last row, you can transform this board as follows: 0) ...PPP - initial configuration 1) ..P..P - jump left 2) ...P.P - move right 3) ...PP. - move left 4) .....P - jump right

{"P...PP",
 "..P...",
 "......",
 "......",
 "......",
 "......"}

{5,5}

Returns: 9

{"......",
 "......",
 "......",
 "......",
 "......",
 ".PP.P."}

{5,5}

Returns: 2

{"......",
 ".P..P.",
 ".P.P..",
 "P.P.P.",
 ".P.P..",
 "......"}

{5,5}

Returns: 11

{".....P",
 "......",
 "P.....",
 "......",
 "......",
 "P....."}

{5,5}

Returns: 12

{"P.....",
 "......",
 "......",
 "......",
 "......",
 "......"}

{4,4}

Returns: -1

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.