Connection Status:
Competition Arena > StarAdventure

StarAdventure

SRM 208 · 2004-08-18 · by AdminBrett

SRM 208 · 2004-08-18 · by AdminBrett · Dynamic Programming, Recursion
Class Name: StarAdventure
Return Type: int
Method Name: mostStars
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The latest version of your favorite adventure game has just been released. On each level you search for stars that earn you points. Simply moving over a location containing stars allows you to acquire them. To help you on your journey, you are given an overhead map of the level in a String[]. Each character in level describes the number of stars at that location. You begin in the upper left spot of the map (character 0 of element 0 of level). On the current stage you must move according to the following rules:
  • 1) On the first pass you may only move downward or rightward each move (not diagonally) until you reach the lower right corner.
  • 2) The second pass begins in the lower right corner where the first pass ended, and proceeds back to the beginning using only upward and leftward steps (not diagonal).
  • 3) The final pass, like the first pass, begins in the upper left corner and proceeds to the lower right corner using only rightward and downward (not diagonal) steps.
Once the stars on a spot are claimed, they cannot be claimed again on a future pass. Return the largest possible number of stars that can be acquired.

Constraints

  • level will contain between 2 and 50 elements inclusive.
  • Each element of level will contain between 2 and 50 characters inclusive.
  • Each element of level will contain the same number of characters.
  • Each character in each element of level will be a digit ('0' - '9').
  • Character 0 in element 0 of level will be '0'.
Examples
0)
{"0123456789"
,"0123456789"
,"0123456789"
,"0123456789"
,"0123456789"
,"0123456789"
,"0123456789"
,"0123456789"
,"0123456789"
,"0123456789"}
Returns: 303
1)
{"0234342522",
 "1232142445"}
Returns: 55
2)
{"01",
 "11"}
Returns: 3
3)
{"0999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"
,"9999999999"}
Returns: 450
4)
{"0333111111",
 "1300000000",
 "1330999990",
 "1030999990",
 "1030999990",
 "1010999990",
 "1011000000",
 "1111111111"}
Returns: 195

Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StarAdventure with a public method int mostStars(vector<string> level) · 57 test cases · 2 s / 256 MB per case

Submitting as anonymous