荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: Cube in Labyrinth
发信站: 荔园晨风BBS站 (Sun Mar 28 11:50:00 2004), 站内信件
Cube in Labyrinth
Time Limit: 1.0 second
Memory Limit: 1 000 КБ
There is a cube on the rectangle X × Y board. The cube side with the side
equal to the side of a cell on the board. During one turn the cube may
roll over its edge movnig to the vertically or horizontally neighboring
cell. There may be walls between some cells that are obstacles. The cube may
not roll over the obstacles. The cube may not leave the board.
You are to deturmine the minimal number of turns necessary to move the
cube from the initial point with coordinates A and B to the given final
point with coordinates C and D. Moreover, in the final position the upper
side must be the same as it was in the initial position.
All the numbers are positive integers; 2<= X,Y <= 10.
Input
The first input line contains two numbers X and Y separated with one or
several spaces. Analogously, the second line consists of the numbers A and
B, the third line – of the numbers C and D. Then there amy be an
informtaion about the walls.
After a symbol ‘v’, situated in a separate line, there are pairs of
integers describing the walls. Here the pair of numbers M and N define a
wall between the cells N, M and N+1, M. Each pair of numbers is located in a
separate line.
After a symbol ‘h’, located in a separat line, there are pairs of integers
(analogously to the previous paragraph) describing the horizontal walls.
The pair M, N define a wall between the cells N, M and N, M+1.
Output
The only line containing the minimal number of moves. If such a displacement
is impossible, you should output “No solution”.
Sample Input
10 2
1 1
10 1
v
2 1
6 2
h
4 1
Sample Output
11
--
Long long ago,there is a hero stand at the edge of the land.......
▁▁
▕天外▏
▕飞仙▏
▔▔
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.157]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店