Задачи
Игра с фишками
Игра с фишками
Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из \textbf{W}\textit{×}\textbf{H} клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
\begin{enumerate}
\item Путь должен состоять из отрезков вертикальных и горизонтальных прямых.
\item Путь не должен пересекать других фишек.
\end{enumerate}
При этом часть пути \textit{может} оказаться вне доски. Например:
\includegraphics{https://static.e-olymp.com/content/96/96757541b824ace121e004572c18ec255454fe99.jpg}
Фишки с координатами (\textbf{1},\textbf{ 3}) и (\textbf{4}, \textbf{4}) могут быть соединены. Фишки с координатами (\textbf{2}, \textbf{3}) и (\textbf{5}, \textbf{3}) также могут быть соединены. А вот фишки с координатами (\textbf{2}, \textbf{3}) и (\textbf{3}, \textbf{4}) соединить нельзя -- любой соединяющий их путь пересекает другие фишки.
Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или "мнимых клеток", расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину \textbf{1}).
\InputFile
Первая строка входного файла содержит два натуральных числа: \textbf{W} -- ширина доски, \textbf{H} -- высота доски (\textbf{1} ≤ \textbf{W}, \textbf{H}\textit{ }≤ \textbf{75}). Следующие \textbf{H} строк содержат описание доски: каждая строка состоит ровно из \textbf{W} символов: символ "\textbf{X}" (заглавная английская буква "\textbf{X}") обозначает фишку, символ "\textbf{.}" (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами -- \textbf{X_1}, \textbf{Y_1}, \textbf{X_2}, \textbf{Y_2}, причём \textbf{1} ≤ \textbf{X_1}, \textbf{X_2}\textit{_\{ \}}≤\textit{ }\textit{\textbf{W}}, \textbf{1} ≤ \textbf{Y_1}, \textbf{Y_2}\textit{_\{ \}}≤\textit{ }\textbf{H}. Здесь (\textbf{X_1}, \textbf{Y_1}) и (\textbf{X_2}, \textit{\textbf{Y_2}}) -- координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (\textbf{1},\textbf{ 1})). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел \textbf{0}; этот запрос обрабатывать не надо. Количество запросов не превосходит \textbf{20}.
\OutputFile
Для каждого запроса необходимо вывести одно целое число на отдельной строке -- длину кратчайшего пути, или \textbf{0}, если такого пути не существует.
Входные данные #1
5 4 XXXXX X...X XXX.X .XXX. 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0
Выходные данные #1
5 6 0