HiddenMirrors | Topcoder Archive

Problem Statement

A number of mirrors are placed at 45 degree angles on a grid. Beams of horizontal or vertical light are then shot in from one of the sides, and it is observed where they leave the grid. Given a number of observations and the number of total mirrors, determine the number of possible ways the mirrors could be placed to achieve the observations.

The grid is size by size squares. Each square may be empty, or may have a mirror oriented in one of two ways ('/' or '\'). The total number of mirrors is given to you as mirrors. The observations will be given in border, where each character corresponds to one of the cells adjacent to the border of the size by size grid, ordered clockwise starting at the upper left. For instance, with a 3x3 grid, the characters wrap around the board as shown below (character 0 in the String corresponds to 0 in the diagram and so on, with A=10 and B=11)

  012
 B...3
 A...4
 9...5
  876

Each character in border will be either '.' or an uppercase letter. If it is an uppercase letter, there will be a corresponding character with the same value. These two corresponding characters give the entry and exit point of an observation. For example, the following diagram illustrates a 5x5 grid with two mirrors and two observations. border would be "..B....B.A.......A..".

   ..B..

 . ..|.. .
 . ..|.. .
 A --\-- B
 . ..|.. .
 . ..\-- A

   .....

Definition

Class:: HiddenMirrors
Method:: locate
Parameters:: String, int, int
Returns:: long
Method signature:: long locate(String border, int mirrors, int size)
(be sure your method is public)

Constraints

size will be between 2 and 8, inclusive.
mirrors will be between 0 and 7, inclusive.
border will contain exactly size*4 characters.
border will be as described above, containing exactly 0 or 2 of each uppercase letter, and the other characters '.'.

Examples

```
"..B....B.A.......A.."
```
```
2
```
```
5
```
```
Returns: 1
```
The example from the problem statement. The solution shown is the only one possible.
```
"..B....B.A.......A.."
```
```
3
```
```
5
```
```
Returns: 30
```

"................................"

Returns: 79515672576

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.