Connection Status:
Competition Arena > JumpingOnTheGrid

JumpingOnTheGrid

TCO13 Semifinal 2 · 2013-02-19 · by K.A.D.R

TCO13 Semifinal 2 · 2013-02-19 · by K.A.D.R · Dynamic Programming, Simulation
Class Name: JumpingOnTheGrid
Return Type: long
Method Name: maxEnergy
Arg Types: (vector<string>, int, int)
Problem Statement

Problem Statement

Little Petya likes computer games a lot. Recently he has received one as a gift from his mother. He has reached the final level of this game which can be represented as a rectangular grid described by String[] grid. Every cell of this grid is described by one of the following characters:

  • '#' - represents a cell that contains a wall.
  • '.'(period) - represents an empty cell.
  • '1'..'9', 'a'..'z', 'A'..'Z' - represent a cell that contains a charging station with a given power. Digits '1'..'9' represent numbers from 1 to 9, characters 'a'..'z' represent numbers from 10 to 35, characters 'A'..'Z' represent numbers from 36 to 61.
  • '*' - represents the starting cell.
  • '$' - represents the target cell.

There is exactly one starting cell and exactly one target cell. Both of these cells are empty.

Petya's character is initially located in the starting cell. Every second he can either perform a move or stay in the same cell. If he decides to make a move, he chooses one of the four directions (up, right, down, left) and a positive integer k. After that the character jumps by k cells in the chosen direction. Note that he can't jump over the walls and the destination cell must not contain a wall as well. This action costs k^2 units of energy. For each second Petya's character spends on a cell with a charging station without movement, his energy increases by the power of this charging station.

You are also given ints E and T. At the beginning Petya's character has E units of energy. If the level of energy becomes strictly less than 0 the character dies. Petya's goal is to reach the target cell in not more than T seconds. Return the maximal amount of energy Petya can have at the end, or -1 if he can't reach the destination within T seconds while keeping his character alive. Note that the game ends after exactly T seconds from the beginning, not when the character steps on the target cell.

Constraints

  • grid will contain between 1 and 25 elements, inclusive.
  • All elements of grid will contain the same number of characters.
  • Each element of grid will contain between 1 and 25 characters, inclusive.
  • grid will contain only characters '.', '#', '*', '$', '1'..'9', 'a'..'z', 'A'..'Z'.
  • There will be exactly one character '*' and exactly one character '$' in the grid.
  • T will be between 1 and 1 000 000 000, inclusive.
  • E will be between 1 and 1 000 000 000, inclusive.
Examples
0)
{"*$.", 
 "#1.", 
 "..."}
1
1
Returns: 0

Petya moves his character directly to the target cell. Note that with power 0 the character is still alive.

1)
{"*$.", 
 "#.1", 
 "..."}
1
1000000000
Returns: 0

Even though T is large now, after the first step Petya has no more power, so he cannot reach the charging station.

2)
{"*$.",
 "#2.",
 "..."}
2
10
Returns: 13

The optimal strategy is to move one step to the right, then one step down, then to wait for 7 seconds on the charging station, and finally to move one step up.

3)
{"*$.",
 "#aA",
 "..."}
2
10
Returns: 151
4)
{"*..Z",
 "##..",
 "#...",
 "...$"}
8
4
Returns: 55

One of the possible optimal strategies is to jump by 2 cells to the right, then jump 1 more cell to the right to reach the charging station. After that we can wait for 1 second there and then jump by 3 cells directly to the target cell.

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

Coding Area

Language: C++17 · define a public class JumpingOnTheGrid with a public method long long maxEnergy(vector<string> grid, int E, int T) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous