首页 > ACM题库 > HDU-杭电 > hdu 2997 Chromatron待解决[解题报告]C++
2014
02-24

hdu 2997 Chromatron待解决[解题报告]C++

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

输出:

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

样例输入:

...............
...............
............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
Hint
Four samples are corresponding to first four pictures.


  1. 小说结局***分竹染也说了 花千骨只是为了白子画承认而且 承认喜欢一个人和守护天下 貌似没什么冲突把 如果没有削肉剔骨 也就没最终决战的相爱相杀了 说白了 不是自私无私的问题 就是一个比一个能钻牛角尖 当然 这是小说 是剧情需要

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。