Connection Status:
Competition Arena > Jetpack

Jetpack

SRM 830 · 2022-05-27 · by misof

SRM 830 · 2022-05-27 · by misof · Graph Theory
Class Name: Jetpack
Return Type: int
Method Name: travel
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

You want to travel from 'A' to 'B' in a maze. You have a jetpack to help you cross some pits along the way.

The maze consists of a grid of unit square cells.

  • Some cells are walls ('#'). You cannot enter those.
  • Some cells are floors ('.'). You can walk on those.
  • The characters 'A' and 'B' are the start and the desired end of your journey. Both are unique. Both count as floors.
  • Some cells are pits ('_'). You can hover over those if your jetpack is active.
  • Some cells are charging stations ('C'). They count as floors.

You can move in a sequence of steps. Each step takes 1 second. Each step will take you to a cell that is horizontally or vertically adjacent to your current cell. You cannot enter a wall, you cannot leave the maze (as if there were additional walls all around it), and you cannot enter a cell with a pit if your jetpack has no charges left.

Initially, your jetpack has no charges. Spending T consecutive seconds at a charging station adds one charge to the jetpack. You can do this arbitrarily many times during your travels, possibly at different charging stations. A jetpack can contain an arbitrary large number of charges simultaneously.

Each step onto a cell with a pit consumes one jetpack charge. (Stepping from a cell with a pit onto another cell with a pit still consumes only one charge. Stepping from a cell with a pit onto a floor does not consume any charges.)


Calculate and return the fastest time in which it is possible to reach 'B' from 'A'. If it's impossible to reach 'B', return -1 instead.

Constraints

  • maze will contain between 1 and 50 elements, inclusive.
  • Each element of maze will contain between 1 and 50 characters, inclusive.
  • Each element of maze will contain the same number of characters.
  • Each character in maze will be one of 'A', 'B', 'C', '#', '.', '_'.
  • There will be exactly one 'A'.
  • There will be exactly one 'B'.
  • T will be between 1 and 10^5, inclusive.
Examples
0)
{"A###B",
 "....."}
47
Returns: 6

We need six ordinary steps. Each takes a second.

1)
{"A#.#B",
 "..#.."}
47
Returns: -1

As we cannot make diagonal steps, this maze has no solution.

2)
{"A#.#B",
 ".._C."}
1
Returns: -1

This maze has no solution either. With an empty jetpack we cannot enter the cell with the pit, and thus we cannot get to the charging station.

3)
{"B_C_C_CA"}
10
Returns: 37

One optimal solution: 1 second: Take a step left. 10 seconds: Charge jetpack. (One charge added.) 1 second: Take a step left. (We stepped onto a pit. One jetpack charge is consumed.) 1 second: Take a step left. 10 seconds: Charge jetpack. (One charge added.) 1 second: Take a step left. (We stepped onto a pit. One jetpack charge is consumed.) 1 second: Take a step left. 10 seconds: Charge jetpack. (One charge added.) 1 second: Take a step left. (We stepped onto a pit. One jetpack charge is consumed.) 1 second: Take a step left.

4)
{"___B__.",
 "C#####.",
 "AC....."}
1
Returns: 8

Charging is quick. We should go up, add three charges to the jetpack and fly over the longer sequence of pits.

5)
{"___B__.",
 "C#####.",
 "AC....."}
10
Returns: 31

The same maze but now charging is slower. We should take the longer route that requires less time spent on charging.

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

Coding Area

Language: C++17 · define a public class Jetpack with a public method int travel(vector<string> maze, int T) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous