Maze

Consider a maze built from equilateral triangles, as shown below.

Every vertex is identified by two coordinates x and y, as in the picture. Some edges carry a white circle or a black circle. Two rules govern movement through the maze:

• You may only travel along edges that carry a circle.
• The colors of the circles you pass must alternate: after crossing an edge with a white circle you must next cross one with a black circle, and vice versa. Your very first move may use either a white or a black circle.

Compute the length of the shortest path from the entrance to the exit, where the length of a path is the number of edges (equivalently, circles) it crosses. Such a path is guaranteed to exist.

The first line contains two integers W and H, the width and the height of the maze (1 ≤ W, H ≤ 500).

The second line contains four integers X1 Y1 X2 Y2 (0 ≤ X1, X2 ≤ W; 0 ≤ Y1, Y2 ≤ H): (X1, Y1) is the entrance and (X2, Y2) is the exit.

The following 2H+1 lines describe the edges. Among these lines, the odd-numbered ones (the 1st, 3rd, 5th, …) describe the horizontal edges, and the even-numbered ones (the 2nd, 4th, …) describe the non-horizontal edges. Each line is a string of the characters n, w, and b with no spaces: n means the edge has no circle, w means it carries a white circle, and b means it carries a black circle. Each odd-numbered line has exactly W characters and each even-numbered line has exactly 2W+1 characters.

Print a single integer: the length of the shortest path from the entrance to the exit.