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

[1qsd]

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

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

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

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

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

[мисс_граффити]

С матрицами...
Единственная идея: берем матрицу из нулей и начинаем заполнять ее удавом (как бы рисуем его по клеточкам). Где он есть - ставим 1. Если клеточка, куда хотим поставить 1, уже равна 1 - значит, он пересекает себя.

Минусы метода: ограниченность размера удава (а по этому поводу ничего у нас не говорится), затраты по памяти (удав может быть из 4 клеток, а массив 100*100).

я бы пошла другим путем... но для этого надо знать:
1. является ли использование матриц обязательным условием?
2. можно ли пользоваться динамическими структурами?

[1qsd]

1) можно и не через матрицы
2) можно пользоваться динамическими структурами

[мисс_граффити]

Идея такая: разбиваем удавчика на отрезки, которые записываются в массив (или список). Отдельно горизонтальные, отдельно вертикальные.
Потом сопоставляем каждую вертикальную с каждой горизонтальной и смотрим, пересекаются ли они.

[1qsd]

давайте по порядку
1) как записывать в массив: сами числа или их координаты или еще что-то??
2) и как их же сопоставлять??

мне еще понравилась идея с клеточками. Если заполнять, то наверное из центра матрицы?
Не думаю, что удав будет слишком большой...

[мисс_граффити]

1) мне кажется, тут подойдет запись с тремя полями: координата конца, координата начала и уровень.
то есть для вертикальных линий координата х - константа, она будет уровнем. координата у начала и конца отличается, их и запишем. аналогично для горизонтальных.
2) если уровень вертикальной находится между началом и концом горизонтальной, а уровень горизонтальной - между началом и концом вертикальной, то их можно считать пересекшимися.

да, из центра - самое логичное.
с клеточками, как мне кажется, будет проще написать... но как формализовать ограничения на размер - я пока не знаю.

[1qsd]

А вы можете код с клеточками (во втором сообщении вы предлагали такой способ) хотя бы примерно набросать для матрицы 1000 на 1000??
или, например, для 100 на 100, если нельзя создать 1000x1000??

Сообщение отредактировано: 1qsd - 27.03.2007 0:39

[мисс_граффити]

а сам не хочешь попробовать хотя бы?

[Michael_Rybak]

И уточни еще, что если он не пересекает себя, но касается.

[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'у..
Я не склонен тут выделять касания, поскольку все происходит на дискретной сетке. Я понимаю, что ты хочешь сказать (это, видимо, относится к топологии), но не думаю, что условие задачи трактовалось так. Любое совпадение точек, принадлежащим звеньям (кроме сочленений соседних звеньев) считаю пересечением.
Но я не говорю, что топологический аспект не представляет интереса! Вполне даже может быть..

[Lapp]

Идея такая: разбиваем удавчика на отрезки, которые записываются в массив (или список). Отдельно горизонтальные, отдельно вертикальные.
Потом сопоставляем каждую вертикальную с каждой горизонтальной и смотрим, пересекаются ли они.
...
1) мне кажется, тут подойдет запись с тремя полями: координата конца, координата начала и уровень.
то есть для вертикальных линий координата х - константа, она будет уровнем. координата у начала и конца отличается, их и запишем. аналогично для горизонтальных.
2) если уровень вертикальной находится между началом и концом горизонтальной, а уровень горизонтальной - между началом и концом вертикальной, то их можно считать пересекшимися.

мисс_граффити, по сути я релизовал твою идею (как заметил позже ). Причем, я тоже хотел сначала делать два разных массива, и организовывать рекордом, как ты пишешь. В процессе я все упростил и унифицировал - ушел от рекорда, оставил обычные два массива Х и Y. Процедура-то симметричная.. А пункт 2 просто идентичным получился.. Одинаково мыслим! .

Интересно было бы сделать и матрицу и сравнить размер кода. Так или иначе, парсер строки делать надо.. А сам алгоритм совсем небольшой.

[Michael_Rybak]

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

В таком случае горизонтальные нельзя проверять только с вертикальными. Он ведь может и пройтись как бы вдоль себя.

[Malice]

В таком случае горизонтальные нельзя проверять только с вертикальными. Он ведь может и пройтись как бы вдоль себя.

Такое может случится в одном единственном случае, если последний частично залезет на первый со стороны его начала (20L10L30L10L15) Иначе чтоб ему так пройтись ему придется пересечь и один из смежных (и уже перпендикулярного направления) отрезков.. У Lapp-а обрабатывается неправильно, хотя и 20L10L30L10R15, (где пересечения нет) тоже..

[Michael_Rybak]

10L10L10R10R10R30

[Гость]

О чем я и говорил. Пересекает еще и смежные отрезки - достаточно для того, чтобы сделать вывод.

[Malice]

Эт я был.. Я же имел ввиду случай типа:

[Michael_Rybak]

Он не пересекает смежные отрезки. Я ведь специально спрашивал, считаются ли касания пересечениями.

Добавлено через 42 сек.
Еще ведь можно 10L10L10L20, и тут всё чисто.

[Malice]

Гы В таком случает надо определьтся - включает ли в свою длину очередной отрезок последнюю точку предыдущего. На твоем примере получается квардрат 11х11, пересечения нет, т.к. никто ширину удава в 1-цу не устанавливал и сливаются отрезки только из-за рисования по клеткам. Я думал, что квадрат будет 10х10 и, соответственно, будет иметь общую точку..

[Michael_Rybak]

У меня не получался нигде квадрат 11х11. Получалось то, что ты нарисовал.

[Lapp]

Критику принял.
Думаю..