Вы
являетесь одним из разработчиков новой компьютерной игры. Игра происходит на
прямоугольной доске, состоящей из W×H
клеток. Каждая клетка может либо содержать, либо не содержать фишку (см.
рисунок).
Важной
частью игры является проверка того, соединены ли две фишки путем,
удовлетворяющим следующим свойствам:
- Путь
должен состоять из отрезков вертикальных и горизонтальных прямых.
- Путь
не должен пересекать других фишек.
При
этом часть пути может оказаться вне доски. Например:
Фишки
с координатами (1,3) и (4,4) могут быть соединены. Фишки с координатами (2,3) и
(5,3) тоже могут быть соединены. А вот фишки с координатами (2,3) и (3,4)
соединить нельзя – любой соединяющий их путь пересекает другие фишки.
Вам
необходимо написать программу, проверяющую, можно ли соединить две фишки путем,
обладающим вышеуказанными свойствами, и, в случае положительного ответа,
определяющую минимальную длину такого пути (считается, что путь имеет изломы,
начало и конец только в центрах клеток (или «мнимых клеток», расположенных вне
доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).
Формат входных данных
Первая
строка входного файла содержит два натуральных числа: W
– ширина доски, H – высота доски (1≤W,H≤75).
Следующие H строк содержат описание доски: каждая строка состоит
ровно из W символов: символ «X» (заглавная
английская буква «экс») обозначает фишку, символ «.» (точка) обозначает пустое
место. Все остальные строки содержат описания запросов: каждый запрос состоит
из четырёх натуральных чисел, разделённых пробелами – X1, Y1, X2, Y2, причём 1≤X1,X2≤W,
1≤Y1,Y2≤H.
Здесь (X1, Y1) и (X2, Y2) – координаты фишек,
которые требуется соединить (левая верхняя клетка имеет координаты (1,1)).
Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса;
см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0;
этот запрос обрабатывать не надо. Количество запросов не превосходит 20.
Формат выходных данных
Для
каждого запроса необходимо вывести одно целое число на отдельной строке – длину
кратчайшего пути, или 0, если такого пути не существует.
Примеры
|
stdin
|
stdout
|
|
5
4
XXXXX
X...X
XXX.X
.XXX.
2
3 5 3
1
3 4 4
2
3 3 4
0 0 0 0
|
5
6
0
|
|
4
4
XXXX
.X..
..X.
X...
1
1 3 1
0
0 0 0
|
4
|
