Задача 27 Блохи

На клеточном поле, размером NxM (2≤N,M≤250) сидит Q (0≤Q≤10000) блох в различных клетках. «Прием пищи» блохами возможен только в кормушке – одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.

Формат входных данных

В первой строке входного файла Input.Txt находится 5 чисел, разделенных пробелом: n, m, s, t, q.

N, M – размеры доски (отсчет начинается с 1); S, T – координаты клетки - кормушки (номер строки и столбца соответственно), Q – количество блох на доске. И далее Q строк по два числа – координаты каждой блохи.

Формат выходных данных

Выходной файл Output.txt содержит одно число – минимальное значение суммы длин путей или –1, если сбор невозможен.

Примеры.

Input.txt	Output.txt
4 4 1 1 3 2 3 3 2 3 3	6
5 5 3 4 0	0

В решении используем обход в ширину с использованием двух очередей.

const

nmax=250;mmax=250;

di:array [1..8] of shortint=(1,2,2,1,-1,-2,-2,-1);

dj:array [1..8] of shortint=(-2,-1,1,2,2,1,-1,-2);

var

a:array[-1..nmax+2,-1..mmax+2] of shortint; массив клеточного поля

kol,k,res,kolold,kolnew,n,m,s,t,q:longint; kol-количество блох

i,j:integer; к-номер прыжка

procedure out ; res результат

begin kolold,kolnew-кол-во элементов

assign(output,'output.txt'); в очередях

rewrite(output);

write(res);

close(output);

end;

procedure solve;

var p:integer;

old,new:array[-1..2,-1..1000] of integer; старая и новая очереди

b:array[1..2,1..10000] of byte; массив блох

procedure init;

begin

assign(input,'input.txt');

reset(input);

read(n,m);

read(s,t);

read(q);

for i:=1 to q do read(b[1,i],b[2,i]);

close(input);

end;

begin

init;

for i:=-1 to n+2 do окружаем поле двойным кольцом из -2

for j:=-1 to m+2 do a[i,j]:=-2;

for i:=1 to n do

for j:=1 to m do a[i,j]:=0;

for i:=1 to q do a[b[1,i],b[2,i]]:=-1; вместо блох ставим -1

fillchar(new,sizeof(new),0); очищаем очереди

fillchar(old,sizeof(old),0);

a[s,t]:=-2; на место кормушки ставим -2

old[1,1]:=s;old[2,1]:=t; заносим кормушку в старую очередь

kolold:=1;k:=1;res:=0;

for i:=1 to q do если в кормушке уже есть блохи то их

считаем

if (old[1,1]=b[1,i])and(old[2,1]=b[2,i])

then inc(kol);

repeat повторяем волну до тех пор пока

kolnew:=0; в старой очереди есть элементы

for i:=1 to kolold do пробегаем все элементы старой

очереди

for j:=1 to 8 do просматриваем все возможные ходы

begin из клетки старой очереди

if a[old[1,i]+di[j],old[2,i]+dj[j]]=0 если в клетке куда прыгает блоха 0

then

begin

a[old[1,i]+di[j],old[2,i]+dj[j]]:=k; заносим в клетку номер волны

new[1,kolnew+1]:=old[1,i]+di[j]; и помещаем ее в очередь

new[2,kolnew+1]:=old[2,i]+dj[j];

inc(kolnew);

end;

if a[old[1,i]+di[j],old[2,i]+dj[j]]=-1 если в клетке сидит блоха

then

begin

a[old[1,i]+di[j],old[2,i]+dj[j]]:=k; заносим в клетку номер волны

new[1,kolnew+1]:=old[1,i]+di[j]; и помещаем ее в очередь

new[2,kolnew+1]:=old[2,i]+dj[j];

res:=res+k; увеличиваем результат на к

inc(kol); считаем блоху

inc(kolnew); и увеличиваем кол-во блох в

новой очереди на 1

end;

end;

inc(k); увеличиваем на 1 номер волны

kolold:=kolnew; новую очередь делаем старой

old:=new;

fillchar(new,sizeof(new),0); очищаем новую очередь

until kolold=0;

if kol<q then

begin res:=-1;out;halt;end; если количество найденных

блох меньше количества данных, то

res:=-1 и выходим из программы

end;

begin solve; out;end.

задачина2массивы

Задача 28 Гипер-каналы

«Не плюй в телепорт: вылетит — не поймаешь!»

На зараженной радиацией планете некоторые точки соединены между собой гипер-каналами. Когда человек заходит в гипер-канал в одной точке, он мгновенно оказывается в другой. Все гипер-каналы двусторонние — то есть их можно использовать для перемещения в обоих направлениях (как из первой точки во вторую, так и из второй в первую).

К сожалению, гипер-каналы платные — каждый проход через гипер-канал стоит 10 у.е. Перемещаться по поверхности планеты из одной точки в другую, не используя гипер-каналы, чревато для здоровья (радиация, однако!).

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