Лабиринт, интеллектуальная Задача Опции

[Andrej_87]

ЛЮДИ ОТКЛИКНИТЕСЬ!!! Помогите пожалуйста с задачей. Не могу написать его на паскале. Имеется алгоритм
Матрица размера N*M определяет некоторый лабиринт. B матице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами.

Необходимо определить, можно ли

а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.

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

Алгоритм:
Основная стратегия человека, вошедшего в самый левый вход, состоит в прохождении лабиринта, используя наиболее левые свободные места лабиринта, т.е. он должен двигаться, держась правой рукой за "стенку" лабиринта. Этот процесс можно формализовать следующим образом. Находясь в очередной позиции лабиринта, он должен помнить, с какой стороны он пришел сюда (слева, справа, сверху, снизу), и, руководствуясь этой информацией, вобрать следующее наиболее предпочтительное направление в новую позицию (куда он может пойти и где еще не был). При этом удобно использовать стек, в верхушке которого находятся координаты текущей позиции и направление, по которому в нее пришли. При этом все посещенные клетки метятся. Легко заметить, что если в позицию попали сверху, то наилучшим направлением будет налево, затем вниз, направо, и наконец назад (вверх). Аналогично можно определить наилучшие направления для других случаев.
Эта стратегия повторяется каждым из людей, при этом позиции, помеченные предыдущими людьми, считаются запрещенными для следующих.

[Connected]

Возможно, это тебе поможет:

http://tpxexe.narod.ru/020.html

Сообщение отредактировано: Connected - 20.03.2007 1:12

[Andrej_87]

Спасибо!! Это хоть что-то! Но мне по заданию нужно провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.

[Connected]

К сожалению, я больше ничего подсказать не в силах..

[Lapp]

Задачка меня заинтересовала - я вообще питаю слабость к лабиринтам..
Сначала - видимо, у тебя опечатка:

.. он должен двигаться, держась правой рукой за "стенку" лабиринта.

- наверное, ты имел в виду левую руку. В остальном агоритм в целом правильный. Добавлю только, что рассмотрение "откуда пришел" гораздо легче формализовать, если рассматривать векторное представление. Вектор "скорости" представляет собой пару (dx,dy). Если этот вектор не меняется - то он прибавляется на следующем ходу, представляя движение в прежнем направлении. Но нам нужно:

1. Повернуться налево и попробовать идти.
2. Если не получается, то повернуться направо.
3. Если снова не получается - перейти к п.2

Вот и весь алгоритм. Повороты векторов тривиально делаются обычной матрицей поворота с синусами/косинусами, только тут она состоит из единиц, нулей и минус единиц..

Выкладываю программу прохождения, которую я сваял на скорую руку. Повороты реализованы процедурой. Шаг - тоже (только для ясности). Данные берутся из файла и выглядят примерно так (мой тестовый файл):

1101111110111111111011111111101111111111
1101111110111111111011111111100011111111
1101111100111000100011111110111011111111
1101110001111010101111111110000011111111
1101110011111010100000011111101111111111
1101111001111010111111011111101110000011
1101111101111010111111011100000000111011
1101111101111010000000011101111101111011
1101111100000011111111111101111100000011
1101111100011000000011111101111111111111
1101111111111000000000111100000111111111
1100011111000000000011111111110111111111
1111000000011100000111110000000000000111
1111011111000000111111110111111101110111
1111011111011110111000000000000001110111
1111000000011110000011101101111100000111
1111111111011111111110001101111111111111
1111111111011111111110111100000111111111
1111111111011111100000111111110111111111
1111111111011111101111111111110111111111

Размеры определяются автоматически из файла.
Заметьте, что собственно лабиринт тут окружен бордюром шириной 1 символ. Это значит, что на вертикальных краях нулей встречаться не должно, нули на верхней кромке представляют входы (вместо массива X(i) ), а нули на нижней кромке - выходы (вместо массива y(i) ).
Это все надо записать в файл с названием Labyrinth_0_0.dat

При выводе я уделил достаточное внимание наглядности .
Далее сама прога..

uses
  CRT;

const
  mx=100; nx=100;
  Left=1; Right=-1;
  Trace=-1;

type
  tLabyrinth=array[0..mx,0..nx]of integer;

var
  m,n,m1,n1,x,y,dx,dy,k,l,x0,i,j:integer;
  Lab:tLabyrinth;
  f:text;
  c:char;

procedure Show;
var
  i,j:integer;
begin
  for j:=0 to n1 do begin
    for i:=0 to m1 do begin
      l:=Lab[i,j];
      if l>0 then begin
        TextColor(l+7);
        Write('*');
        TextColor(7)
      end
      else if l=0 then Write(' ')
      else Write('#');
    end;
    WriteLn
  end
end;


procedure Turn(dir:integer; var x,y:integer);
var
  z:integer;
begin
  z:=x;
  x:=dir*y;
  y:=-dir*z
end;


procedure Step(var x,y,dx,dy:integer);
begin
  Turn(Left,dx,dy);
  while Lab[x+dx,y+dy]>0 do Turn(Right,dx,dy);
  x:=x+dx;
  y:=y+dy
end;


begin
  {Read the data file}
  Assign(f,'labyrinth_0_0.dat');
  ReSet(f);
  m1:=-1;
  while not EoLn(f) do begin
    Read(f,c);
    Inc(m1);
    case c of
      '1',' ': Lab[m1,0]:=1;
      '0': Lab[m1,0]:=0
    end
  end;
  ReadLn(f);
  n1:=0;
  while not EoF(f) do begin
    Inc(n1);
    for i:=0 to m1 do begin
      Read(f,c);
      case c of
        '1',' ': Lab[i,n1]:=1;
        '0': Lab[i,n1]:=0
      end
    end;
    ReadLn(f)
  end;
  m:=m1-1; n:=n1-1;
  Close(f);

  {Passing}
  k:=0;
  WriteLn('Labyrinth ',m,'x',n);
  {Probing all the entries}
  for x0:=m downto 1 do if Lab[x0,0]=0 then begin
    Inc(k);
    x:=x0;
    y:=1;
    dx:=0;
    dy:=1;
    while (y>0)and(y<n1) do begin
      Inc(Lab[x,y],Trace);
      Step (x,y,dx,dy);
    end;
    Write('Entry ',k,': ');
    if y=0 then WriteLn('No way!') else WriteLn('Passed.');
    for j:=1 to n do for i:=1 to m do if Lab[i,j]<0 then Lab[i,j]:=k+1;
    Show;
    Write('Press Enter..');
    ReadLn;
    WriteLn
  end;
  WriteLn('Done.')
end.

[Гость]

Большое спасибо!!!

[NTL]

Lapp, гениально