Maze#3014
Consider the following maze made of equilateral triangles:
Each vertex is specified by two coordinates and as shown in the picture. Some edges have either a white or a black circle on them. There are two major rules governing movement in the maze:
It is only allowed to traverse edges that have a circle on them.
When moving through the maze, you must alternate between white and black circles: that is, you are only allowed to traverse an edge with a white circle if the last circle you passed was black, and vice versa. On the very first move, you are allowed to traverse an edge with either a black or a white circle.
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) traversed. You may assume that such a path always exists.
The first line contains two integers and — the width and the height of the maze, respectively (1 \leq W, H \leq 500). The second line contains four integers: X_1\ Y_1\ X_2\ Y_2 (0 \leq X_1, X_2 \leq W; 0 \leq Y_1, Y_2 \leq H). (X_1, Y_1) are the coordinates of the entry point, and (X_2, Y_2) are the coordinates of the exit.
The next 2H + 1 lines describe the edges: odd-numbered lines (rd, th, etc.) specify horizontal edges, and even-numbered lines (th, th, etc.) specify non-horizontal edges. Each such line consists of a string using characters , and , where means there is no circle on the edge, and or means that there is a white or black circle on the edge, respectively. There are no spaces between characters. Specifically, odd lines contain exactly characters, and even lines exactly 2W + 1 characters.
Your program should print a single integer—the length of the shortest path from entrance to exit—in the first (and only) line of the output.
Example 1
1: A simple maze. One possible shortest path is:
(0, 0) \to (1, 0) \to (0, 1) \to (1, 1) \to (1, 0) \to (2, 0) \to (2, 1)
Below is an illustration of the maze and the shortest path:
2: This is the maze depicted in the illustration on the first page. The shortest path is:
(0, 2) \to (1, 2) \to (1, 1) \to (2, 1) \to (2, 0) \to (3, 0) \to (3, 1) \to (3, 2) \to (4, 1) \to (3, 1) \to (3, 0) \to (2, 0)
\to (2, 1) \to (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4) \to (3, 4) \to (3, 3) \to (4, 3) \to (4, 2) \to (5, 2)
(Length: )