Bikeroute

SRM 122 · 2002-12-04 · by chogyonim

Class Name: Bikeroute

Return Type: int

Method Name: fastest

Arg Types: (vector<string>)

Problem Statement

Joe Freshman, the Stanford student, is trying to find the quickest way to get to his class in the morning. His preferred mode of transportation is a bicycle, and different terrains yield different travel times. Given a String[] map which represents the terrain, return the amount of time required for him to reach his class, using the shortest path (in terms of time). Joe may not travel diagonally.

The map will be comprised of the following characters:

@ (at sign) represents the starting and ending location of travel (they should not be considered in the time calculation)

* (asterisk) represents a road, which takes him 1 unit of time to travel

- (dash) represents a sidewalk, which takes him 2 units of time to travel (due to congestion)

. (period) represents grass, which takes him 5 units of time to travel

~ (tilde) represents dirt, which takes him 10 units of time to travel

X (capital letter X) represents a location he cannot travel on (due to a building, construction, etc.)

However, Joe Freshman has also been warned by his friend John Senior, that the Stanford Sheriff's Office has been ticketing bicyclists. Due to a recent city ordinance, biking is only allowed on streets and sidewalks. Therefore, Joe must avoid traveling in any grass or dirt map location that is immediately adjacent to any police officer (including diagonals). Police officers will be designated on map by the capital letter 'P', and that location cannot be traveled.

If it is impossible for Joe to get from the starting point to the ending point (due to untravelable locations or police), return -1.

Notes

If it is impossible for Joe to get from the starting point to the ending point (due to untravelable locations or police), return -1.
Joe is allowed to travel over a location designated with the '@' symbol even if it is adjacent to a police officer.

Constraints

map will contain between 5 and 50 elements, inclusive
each element of map will contain between 5 and 50 elements, inclusive
each element of map will contain the same number of characters as every other element of map
each element of map will only contain the characters (quotes added for clarity) "@*-.~XP"
the character '@' will appear exactly twice in map

Examples

{"@....",
 ".....",
 ".....",
 ".....",
 "....@"}
Returns: 35

{"@****",
 "~~~~*",
 "~~~~*",
 "~~~~*",
 "@****"}
Returns: 11

{"@@***",
 "~~~~*",
 "~~~~*",
 "~~~~*",
 ".****"}
Returns: 0

{"@***X",
 "~~~~X",
 "~~~~X",
 "~~~~*",
 "@****"}
Returns: 30

The fastest path, along the road, is blocked off. The second fastest path is straight down along the left side through the dirt.

{"@***X",
 "~P~~X",
 "~~~~X",
 "~~~~*",
 "@****"}
Returns: 36

The straight dirt path is now blocked off, since Joe can't travel on the dirt adjacent to a police officer. The next best path is (from the top left corner) to go 3 spaces to the right, all the way down, and then continue along the road.

{"@***X",
 "~P~~*",
 "~~P~*",
 "~~~~*",
 "@****"}
Returns: -1

The locations of the two police officers along with the X block all paths between the target locations.

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

Coding Area

Language: C++17 · define a public class Bikeroute with a public method int fastest(vector<string> map) · 35 test cases · 2 s / 256 MB per case