Antichat снова доступен.
Форум Antichat (Античат) возвращается и снова открыт для пользователей.
Здесь обсуждаются безопасность, программирование, технологии и многое другое.
Сообщество снова собирается вместе.
Новый адрес: forum.antichat.xyz
 |
Олимпиадная задача по информатике |

29.11.2009, 11:30
|
|
Новичок
Регистрация: 28.11.2009
Сообщений: 0
Провел на форуме: 37836
Репутация:
0
|
|
Олимпиадная задача по информатике
Кому не трудно, помогите решить, а то я в ступор вошел, не смог решить
На клеточном поле, размером NxM(N от 0 до 2, M от 0 до 250)сидят Q(от 0 до 10000) блох в различных клетках. "Прием пищи" блохами возможен только в кормушке - одна из клеток, заране известная. Блохи перемещаются по полю странным образом,а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.
Формат входных данных:
Входной файл Input.txt содержит в первой строке 5 чисел, разделенных пробелом: N M S T Q. N, M - размеры доски(отсчет начинается с 1); S,T - координаты клетки - кормушки (номер строки и столбца соответственно), Q - количество блох на доске. И далее Q строк по два числа - каждой блохи координата.
Формат выходных данных
Выходной файл Output.txt должен содержать одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.
Заранее благодарен 
|
|
|

29.11.2009, 14:45
|
|
Новичок
Регистрация: 09.03.2009
Сообщений: 5
Провел на форуме: 73259
Репутация:
4
|
|
{--------------------------------------------------------------}
Program Blochi;
const
InpFile = 'input.txt';
Outfile = 'output.txt';
const
Max = 250;
type
Field = Array [-1..Max+2,-1..Max+2] of Byte;
Steps = array [1..8] of -2..2;
const
x:Steps = (-1,1,2,2,1,-1,-2,-2);
y:Steps = (-2,-2,-1,1,2,2,1,-1);
var
n,m,Yk,Xk,q:integer;
f:field;
procedure detectfield;
var
i,j,k,step:integer;
waschanges:boolean;
begin
fillchar(f,Sizeof(f),0);
for i:=1 to 8 do F[Yk+y[i],Xk+x[i]]:=1;
waschanges:=true;
step:=1;
while waschanges do begin
waschanges:=false;
for i:=1 to n do
for j:=1 to M do if f [i,j] = step then
for k:=1 to 8 do
if f[i+y[k],j+x[k]]=0 then begin
f[i+y[k],j+x[k]]:=step+1;
waschanges:=true;
end;
inc(step);
end;
f[yk,xk]:=0;
end;
Procedure initfield;
var
i,y2,x2:integer;
answer:longint;
nosolution:boolean;
begin
assign(input,inpfile);
reset(input);
assign(output,outfile);
rewrite(output);
answer:=0;
nosolution:=false;
read(n,m,yk,xk,q);
if q>0 then detectfield;
for i:=1 to q do begin
read(y2,x2);
if f [y2,x2]=0 then if (y2<>yk)or(x2<>xk) then nosolution:=true;
answer:=answer+f[y2,x2];
end;
if nosolution then writeln(-1)
else writeln(answer);
close(input);
close(output);
end;
begin
initfield;
end.
|
|
|

29.11.2009, 19:05
|
|
Новичок
Регистрация: 28.11.2009
Сообщений: 0
Провел на форуме: 37836
Репутация:
0
|
|
спс большое, помог=)
|
|
|
|
 |
|
Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
|
|
|
|