Версия для печати темы

Автор: Unconnected 14.01.2011 18:14

Привет всем.

Задачка с окончившейся олимпиады (в аттаче, под литерой F). Я, наверное, изначально пошел неправильным путем, решив сделать рекурсией, при таких входных данных любая рекурсия вылетит.. но другого алгоритма придумать не смог. Точнее, примерно-то смог - надо разворачивать коробку, чтобы могла вперед катиться безгранично, и ехать в пункт назначения, но ничего конкретного. Вот решение: (отработало на 32 тестах из 35, баллов не дали ). Да и переделывать уже нервов не было, после 2х дней написания первого варианта))

Небольшое пояснение, если кто-то захочет разобраться в этом кошмаре)
"Запретная" сторона определяется двумя координатами, по воображаемым осям (ноу-хау, блин_)), одна - справа налево, против часовой стрелки (редактировал, было ПО часовой) (обходит грани), вторая - от наблюдателя вперед. За точку отсчета берется сторона на земле (т.е. имеет координаты (1;1)). Если при движении коробки положение запретной стороны изменяется, то изменяется и соответствующая переменная.

{$APPTYPE CONSOLE}

type posn = record
  kubx,kuby,tx,ty:integer; //kubx(y)-координата куба, tx(y) координаты стороны, которая сейчас на земле
end;

type TDvig = record
  let:char;
  dx,dy:integer;
end;

var kub:posn;
    dvig:array[1..4] of TDvig;
    l:char;
    n,m,b,c,d,i,j,max,sc,lo,nlo:integer;
    res:string='';
    left:byte; //1-left; 2-no-left; 3-inaccessible

function canstep(x,y,id:integer):boolean;
var b1,b2,bl1,bl2:integer;
begin
  bl1:=lo-dvig[id].dy;bl2:=nlo-dvig[id].dx;
  if left=1 then begin
    if (bl1>4) or (bl1=1) then begin
      result:=false;exit;
    end;
  end;

  if left=2 then begin
    if (bl2>4) or (bl2=1) then begin
      result:=false;exit;
    end;
  end;

  b1:=kub.tx+dvig[id].dx;
  b2:=kub.ty+dvig[id].dy;

  if b1>4 then b1:=b1-4;
  if b2>4 then b2:=b2-4;

  if b1=0 then b1:=4;
  if b2=0 then b2:=4;

  if (x<=n) and (y<=m) and (x>0) and (y>0) then result:=true else result:=false;
end;

Procedure step(x,y,id:integer);
begin
  kub.tx:=kub.tx+dvig[id].dx;
  kub.ty:=kub.ty+dvig[id].dy;

  if kub.tx>4 then kub.tx:=kub.tx-4;
  if kub.ty>4 then kub.ty:=kub.ty-4;
  if kub.tx=0 then kub.tx:=4;
  if kub.ty=0 then kub.ty:=4;

  kub.kubx:=x;kub.kuby:=y;

  if left=3 then begin
    if dvig[id].dy<>0 then begin
      left:=1;
      lo:=lo-dvig[id].dy;
    end else begin
      left:=2;
      nlo:=nlo-dvig[id].dx;
    end;
  end
  else if left=2 then begin
    nlo:=nlo-dvig[id].dx;
    if nlo=3 then left:=3;
  end else begin
    lo:=lo-dvig[id].dy;
    if lo=3 then left:=3;
  end;
end;

Procedure rec(backx,backy,x,y:integer);
var i,bx,by:integer;
begin
  if (kub.kubx=c) and (kub.kuby=d) then begin
    write(res);
    halt(0);
  end else begin

    for i:=1 to 4 do begin

      bx:=kub.kubx+dvig[i].dx;
      by:=kub.kuby+dvig[i].dy;

      if ((bx<>backx) or (by<>backy)) and canstep(bx,by,i) then begin
        res:=res+dvig[i].let;
        step(bx,by,i);
        inc(sc);
        if sc<=max then rec(x,y,bx,by);
        step(bx-dvig[i].dx,by-dvig[i].dy,i);
        delete(res,length(res),1);
        dec(sc);
      end;
    end;
  end;
end;

Procedure setdvig(ind:byte;l:char;d1,d2:integer);
begin
  with dvig[ind] do begin
    let:=l;
    dx:=d1;
    dy:=d2;
  end;
end;

begin
  assign(input,'delivery.in');
  assign(output,'delivery.out');
  read(n,m,b,c,d);readln;
  read(l);
  max:=4*(m+n);sc:=0;

  nlo:=2;lo:=2;
  case l of
    'L':begin
      lo:=4;
      left:=1;
    end;
    'R':begin
      lo:=2;
      left:=1;
    end;
    'F':begin
      nlo:=2;
      left:=2;
    end;
    'T':begin
      nlo:=3;
      lo:=3;
      left:=3;
    end;
    'B':begin
      nlo:=4;
      left:=2;
    end;
  end;          

  kub.kubx:=1;kub.kuby:=b;
  kub.tx:=1;kub.ty:=1;

  setdvig(1,'F',1,0);
  setdvig(2,'R',0,1);
  setdvig(3,'B',-1,0);
  setdvig(4,'L',0,-1);

  rec(0,0,1,b);
  write('IMPOSSIBLE');
end.