Bikepath

SRM 122 · 2002-12-04 · by chogyonim

Class Name: Bikepath

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, but he has to drive around all of the buildings on campus. Given a String[] map which represents the terrain, return the shortest distance to his class. Each move counts as a distance of 1, and Joe may not travel diagonally.

The map will be comprised of the following characters:

@ (at sign) represents the starting and ending location of travel

. (period) represents a road he can travel on

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

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

Notes

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

Constraints

map will contain between 5 and 20 elements, inclusive
each element of map will contain between 5 and 20 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 '@', 'X', or '.'
the character '@' will appear exactly twice in map

Examples

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

{"@...X",
 ".....",
 "....X",
 ".....",
 "....@"}
Returns: 8

Even though some spots are blocked off, the shortest path is still the same as before.

{"@....",
 "XXXX.",
 ".....",
 "....X",
 "....@"}
Returns: 10

The blocked off locations force Joe to take a longer route than before.

{"@.X..",
 ".X...",
 "X.X..",
 "...X.",
 "....@"}
Returns: -1

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

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

Coding Area

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