Задача F. Потерявшиеся

Автор:А. Кленин, М. Рожков   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Лабиринт размером N x N клеток состоит из стенок, обозначенных символом '#' (ASCII 35), и проходов, обозначенных символом '.' (ASCII 46). В различных клетках лабиринта находятся два путешественника, потерявшие друг друга. Каждый из них полагает, что сможет найти товарища, если будет двигаться по лабиринту в соответствии со своим планом. Первый путешественник на каждую секунду делает шаг вперёд на одну клетку, если это возможно, либо поворачивает направо, если впереди стена. Второй путешественник действует аналогично, но поворачивает налево.

Требуется определить, встретятся ли когда-нибудь путешественники, и, если да, то после скольки шагов. Первоначальные позиции путешественников заданы координатами (x, y) и направлением d — числом 1, 2, 3, 4 для севера, востока, юга и запада соответственно. Позиция (1, 1) находится в северо-западном углу лабиринта.

Формат входного файла

Первая строка содержит значения N x1 y1 d1 x2 y2 d2. Следующие N строк содержат по N символов каждая — описание лабиринта.

Формат выходного файла

Выходной файл должен содержать единственное число — количество шагов до встречи, либо число −1, если встреча не состоится.

Ограничения

2 ≤ N ≤ 10, 1 ≤ x1, y1, x2, y2N.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1 1 1 2 1 1
..
.#
2
2
3 1 2 4 3 2 3
.#.
.#.
.#.
-1

0.097s 0.016s 15