Connection Status:
Competition Arena > SlowTerrain

SlowTerrain

Rookie SRM 6 · 2021-07-14 · by erinn

Rookie SRM 6 · 2021-07-14 · by erinn · Graph Theory, Search
Class Name: SlowTerrain
Return Type: int
Method Name: fastestPath
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are travelling across some uneven terrain in two dimensions. The map of the area in which you are travelling is divided into a 2D grid of cells. Each cell takes a certain amount of time to cross. (The time for a given cell is always the same and does not depend on the direction of travel.)

Your goal is to determine the fastest path from the given starting point to the given destination.


You are given a String[] terrain, where each character represents a single cell of the grid. Characters '0'..'9' represent the amount of time it takes to travel across the cell. 'S' is the starting point, and 'D' is the destination. (Leaving the starting point and entering the destination takes no time at all.)

You can only move horizontally and vertically. More precisely, your movement is a sequence of steps, and in each step you must move from your current cell into one of the cells that share a side with your current cell.

Return the shortest amount of time in which the destination can be reached.

Constraints

  • terrain will contain between 1 and 50 elements, inclusive.
  • Each element of terrain will contain between 1 and 50 characters, inclusive.
  • Each element of terrain will be the same length.
  • Each character in terrain will be '0'-'9', 'S', or 'D'.
  • Exactly one character in terrain will be 'S' and exactly one character will be 'D'.
Examples
0)
{"S32",
 "030",
 "41D"}
Returns: 3

The optimal path is to go down, right, right, down, 0 + 3 + 0 = 3.

1)
{"3D47S6"}
Returns: 11

Note that the start and destination don't have to be at the edges or corners.

2)
{"0S9",
 "09D",
 "000"}
Returns: 0

Sometimes a path with more steps and more changes of direction may be faster to traverse.

3)
{"0S9",
 "89D",
 "000"}
Returns: 8
4)
{"1S9",
 "29D",
 "345"}
Returns: 9

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

Coding Area

Language: C++17 · define a public class SlowTerrain with a public method int fastestPath(vector<string> terrain) · 16 test cases · 2 s / 256 MB per case

Submitting as anonymous