ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1699. Черепахи и повороты

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Для тренировки боевых черепах военные построили прямоугольный полигон размером w × h клеток. Некоторые клетки полигона проходимы для черепах, а некоторые — нет. Черепахи могут перемещаться только параллельно сторонам полигона. Полигон сконструирован таким образом, что существует единственный способ добраться от любой проходимой клетки до любой другой проходимой клетки, не проходя при этом по одной и той же клетке дважды. Известно, что черепахи очень быстро бегают по прямой, но испытывают трудности при повороте на 90 градусов. Поэтому сложность маршрута определяется как количество поворотов, которое придётся совершить черепахе при переходе от начальной до конечной клетки маршрута. Вы должны написать программу, вычисляющую сложность маршрута по его начальной и конечной клетке.

Исходные данные

В первой строке через пробел записаны два целых числа h и w, размеры полигона (1 ≤ w · h ≤ 100000). Далее задаётся карта полигона — h строк по w символов в каждой. Символ «#» обозначает проходимую клетку, а «.» — непроходимую. В (h + 2)-й строке записано целое число q, количество маршрутов, для которых нужно посчитать сложность (1 ≤ q ≤ 50000). В каждой из следующих q строк через пробел записаны четыре целых числа: номер строки и номер столбца начальной клетки маршрута, номер строки и номер столбца конечной клетки маршрута. Гарантируется, что начальная и конечная клетки маршрута являются проходимыми. Строки занумерованы числами от 1 до h сверху вниз, а столбцы — числами от 1 до w слева направо.

Результат

Для каждого маршрута выведите в отдельной строке единственное число: его сложность.

Пример

исходные данныерезультат
5 4
.#..
###.
..##
.##.
....
4
1 2 2 1
2 3 4 3
4 2 3 4
1 2 4 2
1
0
2
3
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009