MarbleCollectionGame
SRM 391 · 2008-02-26 · by stone
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
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.
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 '#'.
{"7"}
Returns: 7
{"0",
"8"}
Returns: 8
{"264",
"3LL"}
Returns: 15
The best route is right, right, down, left and left.
{"6U29",
"4134",
"L847",
"918U"}
Returns: 38
{"8U4L9",
"0183U",
"U8#38",
"2158#",
"L65U7"}
Returns: 44
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MarbleCollectionGame with a public method int collectMarble(vector<string> board) · 112 test cases · 2 s / 256 MB per case