Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Cube in Labyrinth
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 623Accepted: 165


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.


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.


The only line containing the minimal number of moves. If such a displacement is impossible, you should output "no".

Sample Input

10 2
1 1
10 1
2 1
6 2
4 1

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator