Statistics

Problem Statement for "SoFarAway"

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.

Definition

Class:
SoFarAway
Method:
distance
Parameters:
String[]
Returns:
int
Method signature:
int distance(String[] plan)
(be sure your method is public)

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

  1. {"S...D"}

    Returns: 4

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

  2. {"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.

  3. {"SXD", ".X.", "..."}

    Returns: 6

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

  4. {"SD"}

    Returns: 1

  5. {"S.........", "..........", ".........D"}

    Returns: 11

  6. { "S.................................................", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.", "................................................X.", ".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.", ".X............................................X.X.", ".X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.", ".X.X........................................X.X.X.", ".X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.", ".X.X.X....................................X.X.X.X.", ".X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.", ".X.X.X.X................................X.X.X.X.X.", ".X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.", ".X.X.X.X.X............................X.X.X.X.X.X.", ".X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.", ".X.X.X.X.X.X........................X.X.X.X.X.X.X.", ".X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X....................X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.XXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X................X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.XXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X............X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.XXXXXXXXXX.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X........X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.XXXXXX.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X....X.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.XD.X.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.XXXX.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X......X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.XXXXXXXX.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X..........X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.XXXXXXXXXXXX.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X..............X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.XXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X..................X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X......................X.X.X.X.X.X.X.", ".X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.", ".X.X.X.X.X.X..........................X.X.X.X.X.X.", ".X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.", ".X.X.X.X.X..............................X.X.X.X.X.", ".X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.", ".X.X.X.X..................................X.X.X.X.", ".X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.", ".X.X.X......................................X.X.X.", ".X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.", ".X.X..........................................X.X.", ".X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.", ".X..............................................X.", ".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.", ".................................................." }

    Returns: 1297

  7. { "D.................................................", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.", "................................................X.", ".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.", ".X............................................X.X.", ".X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.", ".X.X........................................X.X.X.", ".X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.", ".X.X.X....................................X.X.X.X.", ".X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.", ".X.X.X.X................................X.X.X.X.X.", ".X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.", ".X.X.X.X.X............................X.X.X.X.X.X.", ".X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.", ".X.X.X.X.X.X........................X.X.X.X.X.X.X.", ".X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X....................X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.XXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X................X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.XXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X............X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.XXXXXXXXXX.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X........X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.XXXXXX.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X....X.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.X.SX.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.XXXX.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X......X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.XXXXXXXX.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X..........X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.XXXXXXXXXXXX.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X..............X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.XXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X..................X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X......................X.X.X.X.X.X.X.", ".X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.", ".X.X.X.X.X.X..........................X.X.X.X.X.X.", ".X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.", ".X.X.X.X.X..............................X.X.X.X.X.", ".X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.", ".X.X.X.X..................................X.X.X.X.", ".X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.", ".X.X.X......................................X.X.X.", ".X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.", ".X.X..........................................X.X.", ".X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.", ".X..............................................X.", ".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.", ".................................................." }

    Returns: 1298

  8. { "S.................................................", ".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.", ".X..............................................X.", ".X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.", ".X.X..........................................X.X.", ".X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.", ".X.X.X......................................X.X.X.", ".X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.", ".X.X.X.X..................................X.X.X.X.", ".X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.", ".X.X.X.X.X..............................X.X.X.X.X.", ".X.X.X.X.X.XXXXXXXXXXXX.XXXXXXXXXXXXXXX.X.X.X.X.X.", ".X.X.X.X.X.X..........................X.X.X.X.X.X.", ".X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.", ".X.X.X.X.X.X.X......................X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXX...X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X..................X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.XXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X..............X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.XXXXXXXXXXXX.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X..........X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.XXXXXXXX.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X......X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X...XX.X.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.XD.X.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.....X.X.X..X.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X.XXXX.X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.X......X.X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.X.XXXXXXXX.X.X.X.X.X.X.X.X.X.X.", ".X.X.X...X.X.X.X.X.X..........X.X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.X.XXXX.XXXXXXX.X.X.X.X.X.X.X...X.", ".X.X.X.X.X.X.X.X.X..............X.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X.XXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.X..................X.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.", ".X.X.X.X.X.X.X......................X.X.X.X.X.X.X.", ".X.X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.", ".X.X.X.X.X.X..........................X.X.X.X.X.X.", ".X.X.X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.X.", ".X.X.X.X.X..............................X.X.X.X.X.", ".X.X.X.X.XXXXX.XXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.X.", ".X.X.X.X..................................X.X.X.X.", ".X.X.X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.X.", ".X.X.X......................................X.X.X.", ".X.X.XXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.X.", ".X.X..........................................X.X.", ".X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.", ".X..............................................X.", ".XXXXXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXXXXX.", ".................................................." }

    Returns: 344

  9. {"S...D" }

    Returns: 4

  10. {"S......", ".......", ".......", ".......", ".......", "......D" }

    Returns: 11

  11. {"S......", "X.XXXX.", "D......" }

    Returns: 4

  12. {"S.X.D" }

    Returns: -1

  13. {".SD...." }

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: