Problem Description

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.

Input Format

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 Format

Output the shortest length of the path.

2 1
0 0 2 1
bb
nwwnw
bn

6

5 4
0 2 5 2
nnbnn
nnnwwbwnnnn
nbbbn
nnwbwwbwwnn
bwwww
nnbwbbwwbnn
nwwwn
nnnnbwbbnnn
nnwnn

22

Hint

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