Connection Status:
Competition Arena > TeleportationMaze

TeleportationMaze

SRM 735 · 2018-06-25 · by majk

SRM 735 · 2018-06-25 · by majk · Brute Force, Search
Class Name: TeleportationMaze
Return Type: int
Method Name: pathLength
Arg Types: (vector<string>, int, int, int, int)
Problem Statement

Problem Statement

There is a rectangular maze built on a two-dimensional grid. Each cell of the grid is either an empty corridor or a wall. A corridor is denoted by a period ('.'), a wall is denoted by a hashmark ('#'). You are given the String[] a that contains the map of the maze. Rows and columns of the maze are numbered starting from 0. The character a[r][c] represents the cell in row r, column c.

You are also given the ints r1, c1, r2, and c2. You start in the cell (r1, c1) and your goal is to reach the cell (r2, c2).

You have to move in steps. In each step you can take one of the following actions:

  • Walk to any of the four adjacent cells provided that the target cell is empty. This move takes 1 second.
  • Teleport to the nearest empty cell in any of the four cardinal directions. This move takes 2 seconds.

You are not allowed to make a move that would take you outside the maze.

If reaching the destination is impossible, return -1. Otherwise, return the smallest T such that it is possible to go from (r1, c1) to (r2, c2) in T seconds.

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • Each element of a will contain between 1 and 50 characters, inclusive.
  • All elements of a will have the same length.
  • Each character in each element of a will be either '.' or '#'.
  • Both r1 and r2 will be between 0 and |a|-1, inclusive.
  • Both c1 and c2 will be between 0 and |a[0]|-1, inclusive.
  • The origin and the destination will be distinct.
  • The origin and the destination will both be empty.
Examples
0)
{".##.",
 ".###",
 ".###",
 "...."}
0
0
3
3
Returns: 4

0##2 .### .### ...4 You begin in the cell labeled 0. The optimal solution is to teleport eastwards (to the cell labeled 2) and from there to teleport southwards (to the cell labeled 4). The above solution takes 4 seconds. For comparison, walking southwards three times and then eastwards three times takes 6 seconds total.

1)
{"#.",
 ".#"}
0
1
1
0
Returns: -1

In this situation you have no valid moves. All cells adjacent to the source cell are blocked, so you cannot walk anywhere. There are no other empty cells in your row or column, so you cannot teleport anywhere either. Thus, there is no way to reach the given destination.

2)
{"......",
 "#####.",
 "#.###.",
 "#####.",
 "#.###.",
 "#####.",
 "#....."}
0
0
6
1
Returns: 5

012... #####. #.###. #####. #.###. #####. #54... The digits in the map above show an optimal solution. Each digit corresponds to the number of seconds between the beginning and the moment when you reach that cell.

3)
{"##########","#.####.###",".#########","##########","##########","########.#",".#########","##########","####.#####","######.###"}
8
4
2
0
Returns: -1
4)
{"##########","##########","##########","###.#.##.#","####.#####",".#####.###","#.####.###","##########","####.###.#",".##.#.####"}
9
0
8
4
Returns: 12

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

Coding Area

Language: C++17 · define a public class TeleportationMaze with a public method int pathLength(vector<string> a, int r1, int c1, int r2, int c2) · 71 test cases · 2 s / 256 MB per case

Submitting as anonymous