| Cube in the labirint |
There is a cube on a rectangular field of size X*Y, composed by squares of size 1x1. The sides of the cube fit in one square. The cube can move to horizontaly or verticaly to the next square by rolling over its edge. There are may be walls between squares. Cube can not move(role) through the walls. Also, cube can not leave the field.
You are to determinate the minimal number of moves, needed to take the cube from square (A, B) to square (C, D). In the end point, cube should be lay on the same side on which it was laid in the starting point.
The first line of input contains integers X and Y (2<=X, Y<=10), separated by one or more spaces. Second and third lines contain integers A B and C D in the same format. There may be inforamtion about walls in the following strings.
After symbol "v", in a separate line, there will be a list of pairs of integers, describing vertical walls. Pair of integers N and M set a wall between squares N, M and N+1, M. Each pair on a separated line, with no blank lines in the middle.
Symbol "h", denotes horizontal walls. Pair of integers N and M set a wall between squares N, M and N, M+1.
Your programm should print the minimal number of moves. If target point can not be reached, print "No solution".
10 2 1 1 10 1 v 2 1 6 2 h 4 1
11