ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Internal Contest March'2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Cube in Labyrinth

Time limit: 1.0 second
Memory limit: 64 MB
There is a cube on the rectangular X × Y board. The cube side is equal to the side of a cell of the board. During one turn the cube may roll over its edge moving 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 find 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.

Input

The first input line contains two numbers X and Y separated with one or more spaces. The second line consists of the numbers A and B, and the third line consists of the numbers C and D presented in the same way. Then an information about the walls may follow. All the numbers are integers; 2 ≤ X,Y ≤ 10.
After a symbol ‘v’, located 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 separate line, there are pairs of integers describing the horizontal walls in the same way. 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

inputoutput
10 2
1 1
10 1
v
2 1
6 2
h
4 1
11
Problem Source: II Collegiate Students Urals Programming Contest. Yekaterinburg, April 3-4, 1998
To submit the solution for this problem go to the Problem set: 1301. Cube in Labyrinth