4. Конное путешествиеОграничение медли 3 секундыОграничение
4. Конное странствие
Ограничение времени 3 секунды
Ограничение памяти 256Mb
Ввод horse.in
Вывод horse.out
Территория далёкой страны Чессляндии представляет собой соединенье прямоугольников, расположенных на клетчатой плоскости с вершинами в узлах целочисленной решётки. Прямоугольники могут пересекаться и даже совпадать. В Чессляндии могут находиться острова и анклавы - территории, не связанные непрерывным маршрутом по примыкающим клеточкам с иными долями страны. Обитатель Чессляндии - добропорядочный рыцарь - в поисках приключений решил совершить конное странствие из городка А в город Б. Его жеребец, природно, может ходить только по правилам шахматного жеребца (т.е. за один ход может совершить перемещение на 2 клеточки по горизонтали либо вертикали в любом направлении и сразу на одну клеточку в перпендикулярном направлении). Конь может пересекать границу Чессляндии в процессе хода, но не может завершать ход вне территории Чессляндии, так как странник не собирается заниматься оформлением заграничных виз. Чтоб спланировать своё странствие рыцарь хочет осознать, сумеет ли он на жеребце добраться до пт предназначения, и если сумеет - сколько медли у него займёт дорога. Помогите ему в этом: напишите программку, решающую данную задачку.
Формат ввода
В первой строке входного файла записано единственное целое число n - количество прямоугольников, образующих территорию Чессляндии. В последующих n строчках записаны по 4 целых числа через пробел: xi1, yi1, xi2, yi2 - координаты левой нижней и правой верхней клеточки i-го прямоугольника соответственно (xi1, yi1 - номер столбца и номер строчки левой нижней клетки прямоугольника, xi2, yi2 - номер столбца и номер строчки правой верхней клеточки прямоугольника, столбцы нумеруются слева направо, строчки нумеруются снизу ввысь), 0 xi1, yi1, xi2, yi2 lt; M, 0 xi2 - xi1 lt; m, 0 yi2 - yi1 lt; m. В (n+2)-ой строке также через пробел записаны 2 целых числа - координаты клеточки, в которой размещен город А, в (n+3)-ей строке подобно записаны координаты клеточки, в которой размещен город Б. Ограничения на величины определяются подзадачей. Гарантируется, что клеточки городов А и Б не совпадают и находятся на местности Чессляндии.
Формат вывода
В единственной строке выходного файла необходимо вывести одно целое число: малое количество ходов, которое нужно жеребцу, чтоб добраться из городка А в город Б. Если добраться невозможно, нужно вывести число -1.
Примечания
Система оценивания: полное решение задачки оценивается в 100 баллов. Частичные решения оцениваются при условии полного решения обозначенных подзадач.
Подзадача 1. n = 1, m = M = 10. Балл за подзадачу: 10.
Подзадача 2. n 10, m = M = 10. Нужно решённая подзадача 1. Балл за подзадачу: 20.
Подзадача 3. n 104, m = 100, M = 104. Требуются решённые подзадачи 1 и 2. Балл за подзадачу: 35.
Подзадача 4. n 100, m = M = 109. Дополнительное ограничение: общая площадь Чессляндии не превосходит 106 клеток. Требуются решённые подзадачи 1 и 2. Балл за подзадачу: 35.
program t;
var n, i, a, b, c, d, k, m: integer; x1, x2, x3, y1, y2, y3: array[1..10000] of integer; f1, f2: text;
function icl(x, y: integer): boolean;
var i: integer;
begin
icl:=false;
for i:=1 to n do
begin
if (xgt;=x1[i]) and (ygt;=y1[i]) and (xlt;=x2[i]) and (ylt;=y2[i]) then
begin
icl:=true;
break
end
end
end;
procedure re(st, fn: integer);
var nst, nfn, i, j, jj, xx, yy: integer; eq, ff: boolean;
begin
m:=m+1;
nst:=k+1;
ff:=false;
for i:=st to fn do
begin
for j:=0 to 11 do
begin
if j mod 3=0 then continue;
xx:=x3[i]+trunc(cos(j*pi/6)*3);
yy:=y3[i]+trunc(sin(j*pi/6)*3);
if not icl(xx, yy) then continue;
eq:=false;
for jj:=1 to k do if (xx=x3[jj]) and (yy=y3[jj]) then
begin
eq:=true;
break
end;
if eq then continue;
if (xx=c) and (yy=d) then
begin
ff:=true;
break
end;
k:=k+1;
x3[k]:=xx;
y3[k]:=yy;
end;
if ff then break;
end;
if ff then exit;
nfn:=k;
if nstgt;nfn then
begin
m:=-1;
exit
end;
re(nst, nfn)
end;
begin
assign(f1, 'horse.in');
reset(f1);
assign(f2, 'horse.out');
rewrite(f2);
readln(f1, n);
for i:=1 to n do readln(f1, x1[i], y1[i], x2[i], y2[i]);
readln(f1, a, b);
readln(f1, c, d);
k:=1;
x3[1]:=a;
y3[1]:=b;
m:=0;
re(1, 1);
writeln(f2, m);
close(f1);
close(f2)
end.
-
Вопросы ответы
Статьи
Информатика
Статьи
Математика.
Разные вопросы.
Разные вопросы.
Математика.
Разные вопросы.
Математика.
Физика.
Геометрия.
Разные вопросы.
Обществознание.