Удав, Задача на координаты и направление Опции

[1qsd]

Помогите решить вот эту несложную задачу. Преподаватель говорит, что решать её нужно как то через матрицы.

Удав расположен в виде нескольких линий, из которых каждая следущая перпендикулярна предыдущей. Направление каждой линии и её протяженность задаются буквами "L" , "R" и числом.

Например 25L15R5 ("25" - длина линии = 25, "L" - поворачивает на 90 градусов влево, "15" - длина линии = 15 , "R" - поворачивает на 90 градусов вправо , "5" - длина линии = 5).

Определить, пересечет ли он себя.

Сообщение отредактировано: 1qsd - 26.03.2007 19:17

[Lapp]

По ходу дела, посмотрев на все сложности, возникшие в геометрическом методе (надеюсь, они все все же преодолены ), я решил написать программку по методу "матрицы".
Получилось действительно намного проще, на ее написание ушло замееееетно меньше времени. Я использую симметричный байтовый массив, который, если удовлетворять ограничениям ТР, не должен превышать 64К. Это значит, если округлить, что поле выходит примерно от -100 до 100 по каждой координате.. Разумеется, ситуация намного улучшится в FPC (например на 1 ГБ памяти можно сделать поле от -15000 до +15000), но все равно вряд ли кто станет спорить, что геометрическое решение лучше в смысле эффективности (хотя, при большом количестве поворотов и небольшом диаметре они все же могут конкурировать).. Правда, остается еще вариант со сжатием матрицы на лету - но это уже извращение..

Хотя, разве не извращение уже и то, что я потратил несколько часов на эту задачу?
Надеюсь, не совсем зря..

{Search for Boa crossings, matrix method}
{by Lapp}

const
  m=100; n=100;

var
  Z:array[-m..m,-n..n]of byte;
  x,y,dx,dy,e,l,b:integer;
  s:string;
  c:char;
  f:file of char;

begin
  dx:=1; dy:=0;
  x:=0; y:=0;
  FillChar(Z,SizeOf(Z),0);
  Z[0,0]:=1;
  Assign(f,'boa.dat');
  Reset(f);
  while not EoF(f) do begin
    Read(f,c);
    c:=UpCase©;
    if c in['0'..'9'] then s:=s+c;
    if (c in['L','R'])or EoF(f) then begin
      Val(s,l,e);
      while l>0 do begin
        Inc(x,dx);
        Inc(y,dy);
        if Z[x,y]=1 then begin
          WriteLn('Crossing at ',x,',',y);
          Halt
        end
        else Z[x,y]:=1;
        Dec(l)
      end;
      s:='';
      case c of
        'L':begin b:=dx; dx:=-dy; dy:=b end;
        'R':begin b:=dx; dx:=dy; dy:=-b end;
      end
    end
  end;
  WriteLn('No crossings')
end.

[Malice]

Теперь я думаю, как говорится, тема раскрыта Я б вчера ответил и поговорил на эту тему, но, блин, пошел ребенка укладывать и сам заснул Но все же для меня вопрос остался открыт: как правильно представить удава - в векторном виде (тогда имеются общие точки в углах и начало в точке 0х0) или кубиками (тогда по идее 0х0 не занята (хотя в последнем примере ты ее занял, что не дало пройти тест by Michael_Rybak 10L10L10L20) и отрезки друг к другу прикасаются, но общих точек не имеют.. Наверно правилен матричный способ (я сначала тоже векторным начал (к рекурсии свалился ) и на нем остановиться, жаль только с размерностью неуниверсально получается