MirrorPath

SRM 237 · 2005-04-06 · by legakis

SRM 237 · 2005-04-06 · by legakis · Geometry, Simple Math, Simple Search, Iteration

Show categories

Class Name: MirrorPath

Return Type: String[]

Method Name: path

Arg Types: (vector<string>)

Problem Statement

NOTE: This problem statement contains an image that may not display properly if viewed outside of the applet.

You will be given the map of a maze containing mirrors. There will be exactly two openings on the boundary of the maze. A laser shined through one opening will reflect off the mirrors and exit through the other opening. You are to write a method that outputs the map of the maze with the laser's path drawn in it.

Mirrors are always at a 45-degree angle to the axis of the maze, and deflect the laser at a right angle. The maze will consist of walls ('#'), open spaces ('.'), and mirrors ('/' and '`') arranged on a regular grid. Your method should replace some or all of the '.' characters in the map with '|', '-', and '+' characters, indicating the open spaces where the laser travels vertically, travels horizontally, and crosses its own path, respectively.

For example, given the following three mazes:


    #######    #######    #######
    ##....#    ##/..`#    ##/..`#
    ##.##.#    ##.##.#    ##.##.#
    ##.##.#    ##.##.#    ##.##.#
    ..`...#    ...../#    ../../#
    ##.####    ##.####    ##.####
    ##.####    ##.####    ##.####

the laser would be reflected as shown in the following figure:

and the solutions for each of these three examples are as follows:


    #######    #######    #######
    ##....#    ##/--`#    ##/--`#
    ##.##.#    ##|##|#    ##|##|#
    ##.##.#    ##|##|#    ##|##|#
    --`...#    --+--/#    --/--/#
    ##|####    ##|####    ##|####
    ##|####    ##|####    ##|####

Note that the laser can bounce of both sides of the same mirror.

Notes

Since '\' is a special character, we will use the '/' (forward slash) and '`' (back quote) characters to indicate mirrors in the input.

Constraints

map will contain between 3 and 50 elements, inclusive.
The length of each element of map will be the same, and be between 3 and 50, inclusive.
map will contain only the characters '#', '.', '/', and '`'.
Exactly 2 characters on the boundary of map will be '.'. All other characters on the boundary will be '#'.
The characters in the four corners of map will be '#'.
The map will be such that if a laser is shined through one opening on the boundary, it will exit through the other opening.

Examples

{ "#.#",
  "#.#",
  "#.#" }
Returns: {"#|#", "#|#", "#|#" }

{ "############",
  "#######/....",
  "######//####",
  "#####//#####",
  "####//######",
  "..../#######",
  "############" }
Returns: {"############", "#######/----", "######//####", "#####//#####", "####//######", "----/#######", "############" }

{ "##.#####",
  "##./`/`#",
  "#/..../#",
  "#`....`#",
  "##`/`/.#",
  "######.#" }
Returns: {"##|#####", "##|/`/`#", "#/++++/#", "#`++++`#", "##`/`/|#", "######|#" }

{ "###",
  "...",
  "###" }
Returns: {"###", "---", "###" }

{ "###",
  "#/.",
  "#`.",
  "###" }
Returns: {"###", "#/-", "#`-", "###" }

{ "#######",
  "##/..`#",
  "##.##.#",
  "##.##.#",
  "...../#",
  "##.####",
  "##.####" }
Returns: {"#######", "##/--`#", "##|##|#", "##|##|#", "--+--/#", "##|####", "##|####" }

This is the second example in the problem statement.

{ "###########.#",
  "#/........./.",
  "#.#########.#",
  "#`........./#",
  "#############" }
Returns: {"###########|#", "#/---------/-", "#|#########|#", "#`---------/#", "#############" }

This is similar to the third example in the problem statement.

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

Coding Area

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