Connection Status:
Competition Arena > SoFarAway

SoFarAway

Rookie SRM 3 · 2021-03-05 · by erinn

Rookie SRM 3 · 2021-03-05 · by erinn · Geometry, Graph Theory
Class Name: SoFarAway
Return Type: int
Method Name: distance
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a String[] plan that describes a rectangular grid of cells. Each character in plan represents one of the cells. Most cells are walls ('X') or open areas ('.'). Two of the cells are special: Your starting location is labelled 'S' and your destination is labelled 'D'. (Both special cells are considered open areas.)

A move consists of moving up, down, left or right by one cell. You may not enter cells that are walls and you are not allowed to leave the grid.

Calculate and return the smallest number of moves that can get you from the starting point to the destination. If it is impossible to reach the destination from the given starting location, return -1 instead.

Notes

  • The dimensions of the rectangle described by plan aren't given explicitly. You can determine the number of rows by looking at the number of elements in plan and the number of columns by looking at the number of characters in plan[0].

Constraints

  • plan will contain between 1 and 50 elements, inclusive.
  • Each element of plan will contain between 1 and 50 characters, inclusive.
  • Each element of plan will contain the same number of characters.
  • Each character of each element of plan will be '.', 'X', 'S', or 'D'.
  • There will be exactly one 'S' in plan.
  • There will be exactly one 'D' in plan.
Examples
0)
{"S...D"}
Returns: 4

Here, you're simply four steps away from where you want to go.

1)
{"S.X.D"}
Returns: -1

Same as above, but there's a wall in your way, so you can't get where you want to go.

2)
{"SXD",
 ".X.",
 "..."}
Returns: 6

You have to move around the wall to get to your destination.

3)
{"SD"}
Returns: 1
4)
{"S.........",
 "..........",
 ".........D"}
Returns: 11

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

Coding Area

Language: C++17 · define a public class SoFarAway with a public method int distance(vector<string> plan) · 13 test cases · 2 s / 256 MB per case

Submitting as anonymous