TopCoder problem "JollyJumpers" used in SRM 376 (Division II Level Three)



Problem Statement

    

You are playing a board game called Jolly Jumpers. The game begins with some number of pawns on a 4x4 board. On each turn, you must either:

  1. Have one pawn jump over another pawn vertically. To do this, the jumping pawn must be vertically adjacent to the pawn it is to jump, with an empty space on the far side. The jumping pawn moves to the empty space, while the jumped pawn is removed from the game. Jumping a pawn scores two points.
  2. Move a pawn one space horizontally. The space it moves to must be empty. Moving a pawn means you lose one point.

You start the game with a score of zero points, and the goal of the game is to score as high as possible. You may stop moving at any time, including before your first move. The layout of the board will be given to you in the String[] layout, the first element of which represents the topmost row of the board. Empty squares will be denoted with the '.' character and pawns will be denoted with '#'.

 

For the layout given, return the maximum score you can achieve using any number of moves.

 

Definition

    
Class:JollyJumpers
Method:maxScore
Parameters:String[]
Returns:int
Method signature:int maxScore(String[] layout)
(be sure your method is public)
    
 

Constraints

-layout will contain 4 elements.
-Each element of layout will contain exactly 4 characters.
-Elements of layout will contain only '.' and '#' characters.
 

Examples

0)
    
{
"....",
".#..",
"..#.",
"...."}
Returns: 1
Move either piece horizontally (-1 point), then jump vertically (+2 points).
1)
    
{
"....",
"....",
"....",
"...."}
Returns: 0
Not the most exciting layout...
2)
    
{
".#..",
".#..",
"..#.",
"...#"}
Returns: 4
3)
    
{
"####",
"####",
"####",
"####"}
Returns: 0
You can't move outside the board, so there's no moves available.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10796&pm=8261

Writer:

jmzero

Testers:

PabloGilberto , Olexiy , misof , ivan_metelsky

Problem categories:

Math, Simulation