dejavu1337

04.05.2021 06:32

Информатика

Есть ответ 👍

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.

126

260

Посмотреть ответы 2

Ответы на вопрос:

nmedvedeva20018

Информатика

4,7(36 оценок)

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;

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.

Евдокия47

Информатика

4,4(49 оценок)

Ответ: рассказ.txt (d)

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Информатика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.