Minimum Mirror Rotations for a Laser Exit
Hudson River Trading● HardFULLTIMEOAProblem statement
You are given a rectangular grid containing empty cells (.), slash mirrors (/) and backslash mirrors. The top-left cell is empty. A laser starts there and moves East.
The beam travels straight through empty cells. A slash mirror turns East to North, North to East, South to West, and West to South. A backslash mirror turns East to South, South to East, West to North, and North to West.
Before the laser starts, you may rotate any set of mirrors by 90 degrees. A rotation changes a slash to a backslash or a backslash to a slash. Each mirror keeps its chosen orientation for the entire path, even if the beam visits it again.
Find the minimum number of rotated mirrors that makes the beam leave the grid from the bottom-right cell while moving East or South. Merely reaching that cell is not enough if its mirror sends the beam back inside the grid. Return -1 if no choice works.
Function
minimumMirrorRotations(grid: String[]) → intExamples
Example 1
grid = ["...\\",".\\/.","\\../"]return = 1With no rotations, the beam turns South at (0, 3), West at (2, 3), and North at (2, 0), then leaves through the top-left cell. Rotate the mirror at (2, 3) from a slash to a backslash. The beam now turns East there and leaves from the bottom-right cell. Zero rotations fail and one rotation works, so the minimum is 1.
Example 2
grid = ["../","...","../"]return = 2The top-right slash must become a backslash so the beam travels South. It then reaches the bottom-right mirror. That slash must also become a backslash so the beam leaves East. Rotating only the first mirror reaches the target cell but sends the beam West, so both rotations are needed.
Constraints
1 <= grid.length <= 121 <= grid[i].length <= 12- All rows have the same length and contain only empty cells, slash mirrors or backslash mirrors.
- The grid contains at most 16 mirrors.
- The top-left cell is empty.