TopCoder problem "MarbleCollectionGame" used in SRM 391 (Division II Level Three)



Problem Statement

    

A marble game is played on a board, each cell of which may contain a number of marbles. Your task is to collect as many marbles as possible using a robot on the board. The layout of the board is given in the String[] board, where each cell is marked with a digit ('0'-'9'), '#', 'U' or 'L'. Each digit represents the number of marbles in that cell. There are no marbles in cells that are not marked with digits.

The robot starts in the upper left cell, which is the first character of the first element of board. During each turn, it can move according to the following rules:

  • The robot can't move out of the board.
  • The robot can't enter a cell marked '#'.
  • The robot may move either right or down one step from any cell.
  • The robot may move up one step from a cell marked 'U'.
  • The robot may move left one step from a cell marked 'L'.

When the robot enters a cell for the first time, it collects all the marbles from that cell. That cell will no longer contain any marbles for the rest of the game. Return the maximum total number of marbles the robot can collect.

 

Definition

    
Class:MarbleCollectionGame
Method:collectMarble
Parameters:String[]
Returns:int
Method signature:int collectMarble(String[] board)
(be sure your method is public)
    
 

Constraints

-board will contain between 1 and 20 elements, inclusive.
-Each element of board will contain between 1 and 20 characters. inclusive.
-Each element of board will contain the same number of characters.
-Each element of board will contain only digits ('0'-'9'), '#', 'U' and 'L'.
-The first character of the first element of board will not be '#'.
 

Examples

0)
    
{"7"}
Returns: 7
1)
    
{"0",
 "8"}
Returns: 8
2)
    
{"264",
 "3LL"}
Returns: 15
The best route is right, right, down, left and left.
3)
    
{"8U4L9",
 "0183U",
 "U8#38",
 "2158#",
 "L65U7"}
Returns: 44
4)
    
{"039LLLU",
 "953348#",
 "0L87#29",
 "718#4#U",
 "594U196"}
Returns: 55

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11125&pm=8488

Writer:

stone

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Dynamic Programming, Graph Theory