|
||||||||||||||||||||||||
|
Заочный тур Московской городской олимпиады школьников по программированию
Задача G. Игра с фишками
| Имя входного файла: | g.in |
| Имя выходного файла: | g.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 32 мегабайта |
Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из WxH клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
1. Путь должен состоять из отрезков вертикальных и горизонтальных прямых.
2. Путь не должен пересекать других фишек.
При этом часть пути может оказаться вне доски. Например:
Фишки с координатами (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, если такого пути не существует.
Примеры
| g.in | g.out |
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 |