시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
An explorer John is now at a crisis! He is entrapped in a W times H rectangular room with a embrasure of laser beam. The embrasure is shooting a deadly dangerous laser beam so that he cannot cross or touch the laser beam. On the wall of this room, there are statues and a locked door. The door lock is opening if the beams are hitting every statue.
In this room, there are pillars, mirrors and crystals. A mirror reflects a laser beam. The angle of a mirror should be vertical, horizontal or diagonal. A crystal split a laser beam into two laser beams with θ±(π/4) where θ is the angle of the incident laser beam. He can push one mirror or crystal at a time. He can push mirrors/crystals multiple times. But he can push up to two of mirrors/crystals because the door will be locked forever when he pushes the third mirrors/crystals.
To simplify the situation, the room consists of W times H unit square as shown in figure 1.
Figure 1
He can move from a square to the neighboring square vertically or horizontally. Please note that he cannot move diagonal direction. Pillars, mirrors and crystals exist on the center of a square. As shown in the figure 2, you can assume that a mirror/crystal moves to the center of the next square at the next moment when he push it. That means, you don't need to consider a state about pushing a mirror/crystal.
Figure 2
You can assume the following conditions:
In order to leave this deadly room, he should push and move mirrors and crystals to the right position and leave the room from the door. Your job is to write a program to check whether it is possible to leave the room.
Figure 3 is an initial situation of the first sample input.
Figure 3
Figure 4 is one of the solution for the first sample input.
Figure 4
The first line of the input contains two positive integers W and H (2 < W, H ≤ 8). The map of the room is given in the following H lines. The map consists of the following characters:
The judges also guarantee that this problem can be solved without extraordinary optimizations.
Output "Yes" if it is possible for him to leave the room. Otherwise, output "No".
7 8 ##S#### #.....# S.O...# #.*|..# L..*..# #.O*..D #.@...# #######
Yes
8 3 ###L#### S.../@.# ######D#
Yes
8 3 ##L##### S..\.@.# ######D#
No