Consider the following maze made of equilateral triangles:
Each vertex is described by two coordinates

- it is only allowed to pass edges with circles on them.
- while walking through the maze it is obligatory to alternate white and black circles; i.e. it is only allowed to pass an edge with white circle if the last circle passed was black and vice versa. It is allowed to pass an edge with either black or white circle on it during the first move.
Task
Write a program to find the length of the shortest path from the entrance point to the exit in the maze. The length of the path is defined as the number of edges (or circles) passed. You may assume that such path always exists.
Input Specification
The first line contains two integers
The next n
, w
and b
, where n
means, that there is no circle on the
edge, and w
or b
means that there is white or black circle on the edge respectively. There
are no spaces between these characters. Naturally, odd lines consist of exactly
Output Specification
Your program should output a single integer (the length of the shortest path from entrance point to the exit in the maze) in the first (and the only) line of the output.
Sample Input 1
2 1
0 0 2 1
bb
nwwnw
bn
Sample Output 1
6
Explanation for Sample Output 1
A simple maze. One possible shortest path is
this:
Here is the illustration of the maze and the shortest path:

Sample Input 2
5 4
0 2 5 2
nnbnn
nnnwwbwnnnn
nbbbn
nnwbwwbwwnn
bwwww
nnbwbbwwbnn
nwwwn
nnnnbwbbnnn
nnwnn
Sample Output 2
22
Explanation for Sample Output 2
This is the description of the maze given in the picture on the first page. The shortest path is this:
(Length: 22)
Comments