UVa 10021

10021 - Cube in the labirint

http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10021.html

Summary

BFS

Explanation

Each state records the location of the cube and the direction of the side of the cube. Then do a breadth first search.

Input

1

10 2
1 1
10 1
v
2 1
6 2
h
4 1

Output

11