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 < m, 0 ≤ xi2 - xi1 < m, 0 ≤ yi2 - yi1 < 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.
Gameskill
2
03.10.2019 08:20
1
Другие вопросы по теме Информатика
polinapoluunaa
02.03.2021 18:46
Eduardo0192837465
02.03.2021 18:47
niknameoyy
02.03.2021 18:47
Kannb
12.08.2019 11:30
ruslan5632
12.08.2019 11:25
BLAID1
12.05.2020 09:53
MezarYT
12.05.2020 09:53
МиссПана
12.05.2020 09:53
isaev40daniil14
12.05.2020 09:53
Популярные вопросы
- Вставить буквы и запятые и( не )поставить И с,з и у и у нескладовае и...
3 - Найдите области определения функции: а) б) в)...
1 - 1.Отметь строчку в которуй все слова пишутся не разделно ответь...
3 - Почему тропические леса вечно зеленые?Чем грозит планете сведение экватореальных...
2 - Тест для закрепления 5 класс 1. Верхняя передача мяча выполняется приемом...
2 - Привет хочу поделиться !во как звали Младшего Дубровского в рассказе???...
3 - СОРОЧНО До води масою 120 г додали ZnCi2 масою 5 г. Яка має частка хлориду...
1 - Особый, наиболее совершенной организации общества, обеспечивает господствующее...
3 - Установіть послідовність написання творівА) Міо, мій Міо Б) П ятнадцятирічний...
2 - Коло в писане в рівнобедрений трикутник ділить його бічну сторону на...
2
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 (x>=x1[i]) and (y>=y1[i]) and (x<=x2[i]) and (y<=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 nst>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.