P4651 [BalticOI 2005] Maze (Day1)

You are given the length and height of a parallelogram. You are also given the coordinates of the entrance and the exit. For each side (edge) of the quadrilateral, there are three possible states: black, white, or colorless. You need to find a shortest path such that the colors of the edges you traverse alternate between black and white.

The first line gives the length and height of the parallelogram, with values in $[1,500]$. The second line gives the coordinates of the entrance and the exit. The following character matrix represents the color of each edge of this parallelogram: `n` means colorless, `w` means white, and `b` means black.

Output the shortest length of the path.

For the first testdata: $(0, 0) \rightarrow (1, 0) \rightarrow (0, 1) \rightarrow (1, 1) \rightarrow (1, 0) \rightarrow(2, 0) \rightarrow (2, 1)$  For the second testdata: $(0, 2) \rightarrow (1, 2) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow \\ (3, 0) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (4, 1) \rightarrow (3, 1) \rightarrow \\ (3, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2) \rightarrow \\ (1, 3) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow \\ (4, 3) \rightarrow (4, 2) \rightarrow (5, 2)$  Translated by ChatGPT 5