Chromatron

Do you remember, during our high school, we did so much homework about light and mirror? “Draw a normal line, then calculates the angle of incidence and the angle of reflection.” So familiar! And I also remember, in that time, I was deeply attracted by a game called Chromatron.
Chromatron is a game all about reflections. Laser beams and many kinds of tools can be used in order to allow the pinwheels being hit by the correct lights that have the same color.
If you’ve played before, you will know that this game uses a very complicated (or you may say mysterious) way to store the current condition. If you press Ctrl+C on its interface and paste it somewhere, you will get code like “1-15-tJoIHWhNHAcgJnmxhCOx” which represents the first picture. And a question comes to my mind, what do those characters exactly mean?




After researching for a long time, I’ve finally got what I want. Here comes:
Two dashes separate the string into three parts. The first two parts denotes the version and level you are playing, which tell the system which initial situation should be load. The third part, tell the system how and where the tools are placed in the table.

But one question still remains, how does the tools being indicated?
In order to figure it out, I divide the string into several continuous units, two characters per unit. Follow the rules below, we can easily infer the position and the way each tool placed.
rotate 0 degree: location is from aa to eq (Figure 1)
rotate 45 degrees (clockwise): location is from fz to jP
rotate 90 degrees (clockwise): location is from kY to po
rotate 135 degrees (clockwise): location is from qx to uN
rotate 180 degrees (clockwise): location is from vW to Am
rotate 225 degrees (clockwise): location is from Bv to FL
rotate 270 degrees (clockwise): location is from GU to Lk
rotate 315 degrees (clockwise): location is from Mt to QJ

“If you give me the initial situation and the tools in this string’s order, I can determine whether it is a solution for you.” Somebody says.
“Yes, that’s exactly what I want you to do.”
This game can be downloaded at http://www.silverspaceship.com/chromatron/. I assure you that it’s exactly the same with this problem.

There are multiple test cases in the input.
First, you’ll get a 15*15 matrix which indicates the initial situation of the table, characters are defined below:
We define the fields as:
. : Empty grids
* : Grids that have walls
- : Conduits that only allow the light going left and right
| : Conduits that only allow the light going up and down
\ : Conduits that only allow the light going top-left and bottom-right
/ : Conduits that only allow the light going top-right and bottom-left

Define laser guns as:
W : White laser gun
R : Red laser gun
G : Green laser gun
B : Blue laser gun

Pinwheel is our target, define them as:
r : Red pinwheel
g : Green pinwheel
b : Blue pinwheel
y : Yellow (Red + Green) pinwheel
m : Magenta (Red + Blue) pinwheel
c : Cyan (Green + Blue) pinwheel
w : White (Red + Green + Blue) pinwheel
n : Black (You should let no light pass it) pinwheel


Following k (k is the number of laser guns) lines, each line represents the initial direction a laser gun points at. Each line has two integers and a string S, two integers represents the position (x, y) which laser gun is being described. S is “u” (up), “d” (down), “l” (left), “r” (right), “lu” (upper-left), “ld” (bottom-left), “ru” (upper-right) or “rd” (bottom-right).

Next line, represents the tools we are using, characters are defined below:
M : Reflector, or mirror, which reflect the light for 90 degrees or reflect back
A : Bender, is an angled reflector, it bends lasers from horizontal and vertical to the diagonals, and vice versa.
S : Splitter. If a laser hits a splitter at the correct angle, it bounces off at an angle (act exactly like a mirror) and also goes straight through. If it hits head on, it just goes through. Notice that the splitter is two-sided.
D : Doppler. The Doppler turns red beams into green, green into blue, and blue into red-or if you go through it backwards, the opposite. At the beginning, the forward direction is left to right.
P : Prism. A prism has two equal short face and a long face, act just like the third picture (Notice that white beam is consists by RGB together), and it reversible and symmetrical.
T : Teleporter. The teleporter causes laser beams to jump instantaneously to the next teleporter in the same direction as beam is travelling. If there’s no teleporter in that direction, the beam disappears.
1 : Red Filter, that only allows red light go through, if the light is a mixed light that contains red light (like white laser), only red light left after passing (if it can pass through).
2 : Green Filter.
3 : Blue Filter.


Last line contains the string S as said before.
You can be sure that all inputs are legal.

At beginning, tools are initially placed as below:


From left to right: A 2 3 1 S M D P

If it’s a solution print “Yes”, otherwise print “No”.

...............
...............
............y..
...............
..r.......c....
...............
...............
W...-.-w-.-b...
...............
.........m.....
...g...........
...............
...............
...............
...............
8 1 r
AAAAA321SS
tJoIHWhNHAcgJnmxhCOx

...............
...............
...............
....g..........
.....b.....g...
......r...b....
.........r.....
G..............
.....r.........
....b...r......
...g.....b.....
..........g....
...............
...............
...............
8 1 ru
MMMMMMMMMMMDD
cpHFIjypclcnHbynphnZoDOyEc

*******W*******
*******.*******
......w........
.*.**.*.*.**.*.
.*...........*.
.*.****.****.*.
.*......w....*.
.*.**.*.*.**.*.
......*w*......
.*.**.*.*.**.*.
.*...........*.
.*.****.****.*.
...***...***...
.*.**.*.*.**.*.
...*r**g**b*...
1 8 d
MMMMAP
NjcAtyiFCddq

.......R.......
...............
...............
...............
...............
...............
...............
.r.T.b.T.r.T.b.
...............
...............
...............
...............
...............
...............
.......B.......
1 8 d
15 8 u
AAAA
DAhKdbxl

Yes
Yes
Yes
Yes

Four samples are corresponding to first four pictures.

2009 Multi-University Training Contest 19 - Host by BNU