Лабіринт#3014

Лабіринт

1 секунда

64 мегабайти

Легка

Розглянемо наступний лабіринт, складений із рівносторонніх трикутників:

Кожна вершина задається двома координатами $x$ та $y$ , як показано на малюнку. Деякі ребра мають або біле, або чорне коло. У лабіринті діють два основні правила руху:

Дозволяється рухатися тільки по ребрах, на яких є коло.
Під час руху по лабіринту потрібно чергувати білі та чорні кола: тобто переходити можна тільки на ребро з білим колом, якщо попереднє пройдене коло було чорним, і навпаки. У першому кроці дозволено переходити на ребро як з білим, так і з чорним колом.

Напишіть програму, яка знаходить довжину найкоротшого шляху від точки входу до виходу в лабіринті. Довжина шляху — це кількість пройдених ребер (або кіл). Можна вважати, що такий шлях завжди існує.

Вхідні дані

Перший рядок містить два цілі числа $W$ та $H$ — ширину та висоту лабіринту відповідно ( $1 \leq W, H \leq 500$ 1 \leq W, H \leq 500). Другий рядок містить чотири цілі числа: $X_{1} Y_{1} X_{2} Y_{2}$ X_1\ Y_1\ X_2\ Y_2 ( $0 \leq X_{1}, X_{2} \leq W$ 0 \leq X_1, X_2 \leq W; $0 \leq Y_{1}, Y_{2} \leq H$ 0 \leq Y_1, Y_2 \leq H). $(X_{1}, Y_{1})$ (X_1, Y_1) — координати входу, а $(X_{2}, Y_{2})$ (X_2, Y_2) — координати виходу.

Наступні $2 H + 1$ 2H + 1 рядків описують ребра: непарні рядки ( $3$ , $5$ , ...) задають горизонтальні ребра, а парні — негоризонтальні. Кожен такий рядок складається з рядка, який містить символи $n$ , $w$ та $b$ , де $n$ означає відсутність кола на ребрі, а $w$ або $b$ означає біле або чорне коло відповідно. Пробілів між символами немає. Зокрема, непарні рядки містять рівно $W$ символів, а парні — рівно $2 W + 1$ 2W + 1 символів.

Вихідні дані

Виведіть одне ціле число — довжину найкоротшого шляху від входу до виходу лабіринту у першому (і єдиному) рядку вихідних даних.

Приклади

Приклад 1

Примітка

1: Простий лабіринт. Один із можливих найкоротших шляхів:

$(0, 0) \to (1, 0) \to (0, 1) \to (1, 1) \to (1, 0) \to (2, 0) \to (2, 1)$ (0, 0) \to (1, 0) \to (0, 1) \to (1, 1) \to (1, 0) \to (2, 0) \to (2, 1)

Нижче наведено ілюстрацію лабіринту та найкоротшого шляху:

2: Це лабіринт, зображений на першій ілюстрації. Найкоротший шлях:

$(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)$ (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)$ \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)

(Довжина: $22$ )