Laser Puzzle

An explorer, John, is in trouble. He is trapped in a $W \times H$ rectangular room. A laser emitter on the wall shoots a deadly beam, and John cannot cross or touch it. The wall also has statues and a locked door. The lock opens when the beam hits every statue.

The room has pillars, mirrors, and crystals. A mirror reflects a laser beam. Its angle is vertical, horizontal, or diagonal. A crystal splits an incoming beam into two beams at angles $\theta \pm \frac{\pi}{4}$, where $\theta$ is the angle of the incoming beam. John can push one mirror or crystal at a time. He can push the same object several times, but he can push at most two mirrors or crystals in total. If he makes a third push, the door locks forever.

The room is a grid of $W \times H$ unit squares (Figure 1). John moves to a horizontally or vertically adjacent square and never diagonally. Pillars, mirrors, and crystals sit at square centers. When John pushes a mirror or crystal, it moves to the center of the next square at the next moment (Figure 2). You do not need to model the pushing state.

The following conditions hold:

• The laser beams travel horizontally, vertically, or diagonally.
• The emitter shoots a beam toward the center of an adjacent square.
• The emitter is on the wall.
• John cannot enter a square with a pillar.
• A mirror reflects a beam at the center of its square, on both sides.
• A mirror parallel to a beam blocks it.
• A crystal splits a beam at the center of its square.
• A diagonal beam does not hit a statue.
• If a horizontal, vertical, or diagonal beam hits the door, John cannot leave the room.

John must push and move the mirrors and crystals into the right positions, then leave through the door. Write a program that checks whether John can leave the room. Figure 3 shows the initial state, and Figure 4 shows one possible solution.

The first line contains two positive integers $W$ and $H$ ($2 < W, H \le 8$). The next $H$ lines give the room map with these characters:

• #: wall of the room
• *: pillar
• S: statue on the wall
• /: diagonal mirror at angle $\frac{\pi}{4}$ from the bottom side of the room
• \: diagonal mirror at angle $\frac{3\pi}{4}$ from the bottom side of the room
• -: horizontal mirror
• |: vertical mirror
• O: crystal
• @: John's initial position
• .: empty floor
• L: laser emitter
• D: door

Print Yes if John can leave the room. Otherwise, print No.