 TURA | Описание На бесконечном клетчатом листе, в котором некоторые клетка могут быть вырезаны, расположена шахматная фигура - ладья. Строки и столбцы листа пронумерованы натуральными числами: 1,2,3... Столбцы пронумерованы слева направо, а строки - снизу вверх. Ладья одним ходом может переместиться на любую другую не вырезанную клетку, которая находится в одной строке или в одном столбце с начальной клеткой. Ладье запрещено проходить через вырезанную клетку. Задача Определите, за какое наименьшее количество ходов ладья может перейти с одного на другое указанные поля (если это вообще возможно), перемещаясь в соответствии с вышеописанными правилами. Входные данные В первой строке текстового файла TURA.DAT даны четыре целых числа x1,y1,x2,y2, разделенные пробелами:
x1 - номер столбца, y1 - номер строки - указывают координаты клетки, где ладья находится вначале x2 и y2, аналогично, указывают координаты клетки, куда ладья должна прийти в конце. Известно, что -109 <=x1,y1,x2,y2 <=109, и ни одна из этих двух клеток не вырезана
Во второй строке файла находится число n - количество вырезанных клеток (n<=1000). Каждая их следующих n строк содержит два целых числа, разделенных пробелом - координаты одной вырезанной клетки. В (k+2)-й строке (1<=k<=n) даны координаты k-й вырезанной клетки: pk - колонка (-109<=pk<=109) и qk - ряд (-109<=qk<=109). Выходные данные В единственной строке текстового файла TURA.REZ должно находиться одно целое число - наименьшее количество ходов, необходимое для перехода ладьи из одной указанной клетки в другую. Если ладью нельзя перевести в заданную клетку, то в единственной строке файла следует вывести слово "NO". Например: TURA.DAT 1 -1 5 -4 4 1 1 5 -5 2 -4 4 -1 TURA.REZ 3 TURA.DAT 10 11 5001 -4733 5 5001 -4732 5001 -4734 1 1 5000 -4733 5002 -4733 TURA.REZ NO
|
|---|