MirrorPlacement

SRM 237 · 2005-04-06 · by legakis

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

Show categories

Class Name: MirrorPlacement

Return Type: int

Method Name: mirrors

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, with exactly two openings on the boundary. Your task is to add mirrors to the maze in such an arrangement that if a laser is shined through one opening in the boundary, it will exit through the other opening. Your method should return the least number of mirrors necessary to be added in order to accomplish this. If no solution is possible, return -1.

The maze will consist of walls ('#'), open spaces ('.'), and mirrors ('/' and '`') arranged on a regular grid. The laser may only travel though open spaces and reflect off of mirrors. If it hits a wall, the light will be absorbed. You may only place mirrors on open spaces.

Mirrors are always at a 45-degree angle to the axes of the maze, and deflect the laser at a right angle.

For example, given the following maze:


    #######
    ##....#
    ##.##.#
    ##.##.#
    ......#
    ##.####
    ##.####

There are three arrangements of mirrors that will deflect the laser from one opening in the boundary to the other:

These three solutions require 1, 3, and 4 mirrors, respectively. The least number of mirrors needed is 1, so 1 is the correct answer.

The map may have mirrors already placed, which you may use but cannot move. For example, given the following map:


    #######
    ##....#
    ##.##.#
    ##.##.#
    ../...#
    ##.####
    ##.####

there is only one solution (the third arrangement in the figure above). Three more mirrors must be added, so the correct answer in this case is 3.

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 '#'.

Examples

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

This is the first example in the problem statement.

{ "########",
  "##....##",
  "##.##.##",
  "##...`..",
  "#####.##" }
Returns: 3

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

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

There are many 2-mirror solutions possible, all with '`' mirrors in the same column of the 3rd and 5th rows.

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

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

No solution is possible.

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

Coding Area

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