Олимпиадная задача по информатике

Discussion in 'Болталка' started by Eclernik, 29 Nov 2009.

  1. Eclernik

    Eclernik New Member

    Joined:
    28 Nov 2009
    Messages:
    0
    Likes Received:
    0
    Reputations:
    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, если сбор невозможен.


    Заранее благодарен :)
     
  2. alexandrgsm

    alexandrgsm New Member

    Joined:
    9 Mar 2009
    Messages:
    4
    Likes Received:
    1
    Reputations:
    0
    {--------------------------------------------------------------}
    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,Xk+x]:=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.
     
  3. Eclernik

    Eclernik New Member

    Joined:
    28 Nov 2009
    Messages:
    0
    Likes Received:
    0
    Reputations:
    0
    спс большое, помог=)