Laser Grid Energized Cells
MediumSimulation · SalesForce
A laser beam travels through a rectangular grid. grid is a list of equal-length strings; each character is one of:
.empty space: the beam continues in the same direction./mirror: a beam moving right turns up, up turns right, left turns down, and down turns left.\mirror: a beam moving right turns down, down turns right, left turns up, and up turns left.|splitter: a beam moving up or down passes straight through; a beam moving left or right is split into two beams, one going up and one going down.-splitter: a beam moving left or right passes straight through; a beam moving up or down is split into two beams, one going left and one going right.
start = [row, col, direction] gives the cell the beam starts in and its direction ("R", "L", "U" or "D"). The tile in the starting cell acts on the beam just like any other cell it enters. After a cell has acted on a beam, the beam moves one cell in its (possibly new) direction. A beam that moves outside the grid disappears.
Beams can go around in loops, so a beam stops being followed as soon as it enters a cell moving in a direction it has already entered that cell with before.
A cell is energized if at least one beam passes through it. Return all energized cells as [row, col] pairs sorted by row, then by column.
Example 1
- Input:
- grid = ["..|.", "....", "/.-."], start = [0, 0, "R"]
- Output:
- [[0, 0], [0, 1], [0, 2], [1, 2], [2, 0], [2, 1], [2, 2], [2, 3]]
- Explanation
- The beam moves right to the
|at (0, 2) and splits: the upward half leaves the grid, the downward half reaches the-at (2, 2) and splits again. The right half exits after (2, 3); the left half hits/at (2, 0), turns down and leaves. 8 cells are energized.
Example 2
- Input:
- grid = ["\\.", ".."], start = [0, 0, "R"]
- Output:
- [[0, 0], [1, 0]]
- Explanation
- The start cell itself holds a mirror, so it acts on the beam immediately:
\turns a right-moving beam downward, the beam passes (1, 0) and leaves the grid. Cell (0, 1) is never reached.
Example 3
- Input:
- grid = ["/-\\", "|.|", "\\-/"], start = [1, 0, "U"]
- Output:
- [[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]]
- Explanation
- The mirrors form a closed loop: the beam travels up, right, down and left around the border and returns to (1, 0) still moving up. That state was already seen, so the simulation stops. The centre cell is never touched.
Constraints
1 <= grid.length, grid[i].length <= 100, and all rows have the same lengthgrid[i][j]is one of.,/,\,|,-startis inside the grid and its direction is one of"R","L","U","D"