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

[1qsd]

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

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

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

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

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

[Lapp]

Я тоже не придумал, как тут использовать матрицы, кроме заполнения поля единицами на месте его тела, но этот способ сильно ограничивает размеры удава и крайне неэффективен по использованию памяти. Была у меня мыслишка сжимать эту "матрицу" на лету, но я все же решил пойти другим путем - традиционным, геометрическим.

Учитывая структуру входной строки, звенья удава все время чередуются: горизонтальное - вертикальное, и снова. Мой алгоритм прост:
1. иду по удаву с начала и до конца
2. координаты текущего звена сравниваю:
- если четное, с нечетными;
- если нечетное, с четными
3. сравнение заключается в оценке на отрицательность или равенство нулю произведения:
(Xi - Xj)*(Xi-1 - Xj) - это для нечетных,
(Yi - Yj)*(Yi-1 - Yj) - это для четных.
Здесь Xi, Xi-1 - координаты текущего звена, а Xj - координата звена, с которым сравниваем (то же самое для Y). Замечу, что я считаю первое звено расположенное началом в т. 0,0 , а конец - в положительном направлении по оси Х. Сиситема координат обычная математическая (х - вправо, у - вверх).

Чуть ли не больше половины занимает парсинг входной строки (простейший) с заполнением массивов координат X и Y. Он делается с помощью поворотов вектора направлений (Dir). Для этого использую матрицу поворотов (аналогично как в теме Лабиринт , но без выделения в отдельную процедуру).

Программа читает из файла boa.dat, в нем не должно быть никаких других символов, кроме L, R и цифр (даже концов строк!). Находит (простите - должна находить! ) все пересечения и сообщает номера пересекающихся звеньев. Если ничего не пересекается - выходит молча .

Я проверял на такой вот строчке:
10R5L6L3L12R5
В ней два пересечения: 2х5, 1х6

Вот сам код:

{ Searching self-crossings of a Boa }
{ by Lapp }
const
  m=100;

var
  x,y:array[0..m]of integer;
  Dir:record
    x,y:integer
  end;
  i,j,n,e,l,z:integer;
  Cross:boolean;
  c:char;
  s:string;
  f:file of char;

begin
  { Data input }
  x[0]:=0; y[0]:=0;
  Dir.x:=1; Dir.y:=0;
  Assign(f,'boa.dat');
  Reset(f);
  n:=0;
  while not EoF(f) do begin
    Read(f,c);
    c:=UpCase©;
    if (c in ['L','R'])or EoF(f) then begin
      Inc(n);
      if EoF(f) then s:=s+c;
      Val(s,l,e);
      x[n]:=x[n-1]+Dir.x*l;
      y[n]:=y[n-1]+Dir.y*l;
      s:='';
      with Dir do case c of
        'L':begin z:=x; x:=-y; y:=z end;
        'R':begin z:=x; x:=y; y:=-z end;
      end
    end
    else s:=s+c
  end;
  { Start working}
  for i:=2 to n do begin
    Cross:=false;
    j:=i mod 2;
    while not Cross and (j<i-2) do begin
      if Odd(i) then
        Cross:=Odd(j) and ((x[i]-x[j])*(x[i-1]-x[j])<=0)
      else
        Cross:=not Odd(j) and ((y[i]-y[j])*(y[i-1]-y[j])<=0);
      if Cross then begin
        WriteLn('Bonds #',j+1,' and #',i,' are crossed over');
        Cross:=false
      end;
      Inc(j,2)
    end
  end
end.

Добавлено через 8 мин.
Да, еще забыл ответить Michael_Rybak'у..
Я не склонен тут выделять касания, поскольку все происходит на дискретной сетке. Я понимаю, что ты хочешь сказать (это, видимо, относится к топологии), но не думаю, что условие задачи трактовалось так. Любое совпадение точек, принадлежащим звеньям (кроме сочленений соседних звеньев) считаю пересечением.
Но я не говорю, что топологический аспект не представляет интереса! Вполне даже может быть..