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

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Пройти лабиринт по правилу правой руки.

Автор: DarkWishmaster 27.03.2011 22:43

Есть лабиринт, надо его пройти по правилу правой руки.
вот к примеру
7 9
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 0 1
1 0 1 0 0 1 0 1 1
1 0 0 0 1 0 0 0 1
1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 1 0 1
1 2 1 1 1 1 1 3 1

1- блок
0 - пусто
2- вход
3- выход
Я знаю как должен вести себя робот, но проблема в том что не могу написать его поведение на Паскале, может вы поможете?
Тут надо помнить в какую сторону смотри робот что-бы можно было знать относительно него какая сторона есть - право а какая -лево
для этого я исп. процедуры:
например если робот смотрит вверх то он идет по x=-1, y=0


    procedure RotD;  //поворачивает направо
        begin
           if (x=0) and (y=1) then begin x:=1; y:=0; exit; end;
            if (x=0) and (y=-1) then begin x:=-1; y:=0; exit; end;
             if (x=-1) and (y=0) then begin x:=0; y:=1; exit; end;
              if (x=1) and (y=0) then begin x:=0; y:=-1; exit; end;
         end;
        procedure RotS; // поворачивает налево
        begin
           if (x=0) and (y=1) then begin x:=-1; y:=0; exit; end;
            if (x=0) and (y=-1) then begin x:=1; y:=0; exit; end;
             if (x=-1) and (y=0) then begin x:=0; y:=-1; exit; end;
              if (x=1) and (y=0) then begin x:=0; y:=1; exit; end;
         end;


  procedure Move;
    begin
     i:=i+x;
     j:=j+y;
end;

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

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

Автор: Freedom 27.03.2011 22:57

Цитата(DarkWishmaster @ 27.03.2011 18:43)

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

а что если тупик, то повернуться не один раз налево а два раза?

Автор: DarkWishmaster 27.03.2011 23:12

Цитата(Freedom @ 27.03.2011 18:57)

а что если тупик, то повернуться не один раз налево а два раза?

Я имел ввиду что если тупик впереди и нельзя повернуть направо то надо налево, извините, исправил.
А если нигде повернуть нельзя то поворачиваем на 180 и придерживаемся правой стены.

Автор: DarkWishmaster 29.03.2011 1:07

Вообщем вот что получилось:


  Program Robot; Uses Crt;
 var a:array[1..100,1..100] of integer;
    i,j,n,m,x,y,flag:integer;  F:text; Q:boolean;
procedure Enter;
       begin
         for i:=1 to n do
          for j:=1 to m do
            if a[i,j]=2 then exit;
       end; {Enter}
    procedure Initiare;
          begin
          assign(F, 'C:\In.TXT');  reset(F);
          read(F, n); readln(F, m);
          for i:=1 to n do   begin
          for j:=1 to m do    begin
          read(F,a[i,j]);
          end;
        readln(F);
      end;
     close(F);
   end; {Initiare}
  procedure Print;
    var i,j:byte;
      begin
        for i:=1 to n do begin
          for j:=1 to m do begin
            write(a[i,j]); end;
             writeln;
              end; {Print} end;
        function Block(i,j:integer):boolean;  // смотрим если можно идти вперёд
           begin
             if (a[i,j]=1) or (i>n) or (j>m) then Block:=True
              else Block:=False;
            end;  (*BlocK*)
         procedure RotD;  // поворот направо
        begin
           if (x=0) and (y=1) then begin x:=1; y:=0; exit; end;
            if (x=0) and (y=-1) then begin x:=-1; y:=0; exit; end;
             if (x=-1) and (y=0) then begin x:=0; y:=1; exit; end;
              if (x=1) and (y=0) then begin x:=0; y:=-1; exit; end;
         end;
        procedure RotS; // поворот налево
        begin
           if (x=0) and (y=1) then begin x:=-1; y:=0; exit; end;
            if (x=0) and (y=-1) then begin x:=1; y:=0; exit; end;
             if (x=-1) and (y=0) then begin x:=0; y:=-1; exit; end;
              if (x=1) and (y=0) then begin x:=0; y:=1; exit; end;
         end;
     procedure Move(var i,j:integer); // шаг вперед
       begin
        i:=i+x;
         j:=j+y;
       end; {move}
     function Exit(i,j:integer):boolean; // проверка на выход
       begin
        if a[i+x,j+y]=3 then Exit:=True else Exit:=False;
      end;
 Begin ClrScr;
   Initiare;
   Enter;
   x:=-1; y:=0;
   flag:=1;
    repeat
 if Block(i+x,j+y)=True then  //если впереди блок тогда 
       begin
       RotD;  // поворачиваем направо
        if Block(i+x,j+y) // если и на право блок то
           then while Block(i+x,j+y)=True do   // поворачиваем налево до тех пор пока найдем свободное пространство
                  RotS
                else Move(i,j); // если после поворота направо нету блока то шаг вперед
       end else Move(i,j); //если впереди нету блока то шаг вперед
    until Exit(i,j)=True;  // выполнять пока не найдем выход
readln;
end.

Для примера массива что я написал выше, он идёт наверх, поворачивает, видет что там тупик, и идёт в обратном направлении пока дойдёт до входа, и опять всё заново

((

З.Ы , как тут спойлер написать? что-бы можно было свернуть весь код.

Там откуда я взял задачу, она по техники Greedy, и есть Подсказка: Выбирать из Множество [Вниз, Вверх, Направо, Налево] так что-бы робот двигался вдоль одной стены.

Автор: TarasBer 29.03.2011 13:20

Ну и жесть вы понаписали.
Я так и не понял, а где вы храните, в какую сторону смотрит робот?


const 
  dx : array [0 .. 3] of integer = (1, 0, -1, 0);
  dy : array [0 .. 3] of integer = (0, 1, 0, -1);

var 
  robot: record
    x, y, direction: integer;// текущее направление тоже надо помнить
  end;

begin
  ...
  for d := robot.direction - 1 to robot.direction + 2 do begin // перебор по направлениям, начиная с того, что направо от текущего
    robot.direction := (d + 4) mod 4;  // просто переводим счётчик цикла к интервалу 0..3
    if free[x+dx[robot.direction], y+dy[robot.direction]] then break; // если туда можно пойти, значит мы нашли нужное направление, выходим из цикла
  end;
end.

> if Block(i+x,j+y)=True then

Да чего уж там, давай сразу
if true=(true=((Block((i+x+0)*1, (j+y+1-1)*1)=true)=true))

Не надо писать =true, ясно? Это тавтология потому что.

Автор: DarkWishmaster 29.03.2011 17:38

Цитата(TarasBer @ 29.03.2011 9:20)

Ну и жесть вы понаписали.
Я так и не понял, а где вы храните, в какую сторону смотрит робот?


const 
  dx : array [0 .. 3] of integer = (1, 0, -1, 0);
  dy : array [0 .. 3] of integer = (0, 1, 0, -1);

var 
  robot: record
    x, y, direction: integer;// текущее направление тоже надо помнить
  end;

begin
  ...
  for d := robot.direction - 1 to robot.direction + 2 do begin // перебор по направлениям, начиная с того, что направо от текущего
    robot.direction := (d + 4) mod 4;  // просто переводим счётчик цикла к интервалу 0..3
    if free[x+dx[robot.direction], y+dy[robot.direction]] then break; // если туда можно пойти, значит мы нашли нужное направление, выходим из цикла
  end;
end.

У меня там переменые x и y меняются в зависимости от того куда смотрит робот
например
если x=-1 y=0 тогда когда мы вызываем процедуру Move(i,j); то он идёт наверх на 1 единицу (i-1, j+0)
т.е он смотри на север.

З.Ы если мы делаем так: IF Ok then то оператор сразу понимает что Ok(boolean) должен быть True?
а для False как? If not ok then ?

Автор: TarasBer 29.03.2011 17:46

> У меня там переменые x и y меняются в зависимости от того куда смотрит робот

Я понял. У тебя x, y - это вектор сдвига, а i, j - координаты.
Плохие названия, неговорящие.

Обычно x, y - координаты, а dx, dy - вектор сдвига.
Но в данном случае как раз проще хранить в качестве направления именно число от 0 до 3.

> З.Ы если мы делаем так: IF Ok then то оператор сразу понимает что Ok(boolean) должен быть True?
а для False как? If not ok then ?

Ну да.
Это должно быть очевидно, если понимать, что заголовок оператора if - это любое выражение типа boolean. Это может быть как переменная этого типа ( if b then ... ), так и оператор, возвращающий значение этого типа ( if x>y then ... ).

Добавлено через 1 мин.
> if (a[i,j]=1) or (i>n) or (j>m) then Block:=True
else Block:=False;

Тоже типичный бульщит (bool shit)

А сразу почему не написать

Block := (a[i,j]=1) or (i>n) or (j>m);

Автор: DarkWishmaster 29.03.2011 17:54

Tarasber, спасибо, исправлюсь, пока в привычку не вошло.

Автор: DarkWishmaster 30.03.2011 22:17


Program Robot_Greedy; Uses Crt;
const
  dx : array [0 .. 3] of integer = (1, 0, -1, 0);
  dy : array [0 .. 3] of integer = (0, 1, 0, -1);
type matrice=array[1..100,1..100] of integer;
var
  a,b:matrice;
    i,j,n,m,x,y,d,flag:integer;  F:text;
    Robot: record
      x, y, direction: integer;
          end;
procedure Enter;   {Find Entrance}
       begin
         for i:=1 to n do
          for j:=1 to m do
            if a[i,j]=2 then exit;
       end; {Enter}
    procedure Initiare;
          begin
          assign(F, 'C:\In.TXT');  reset(F);
          read(F, n); readln(F, m);
          for i:=1 to n do   begin
          for j:=1 to m do    begin
          read(F,a[i,j]);
          end;
        readln(F);
      end;
     close(F);
     for i:=1 to n do
      for j:=1 to n do
       if a[i,j]=0  then b[i,j]:=0 else b[i,j]:=-1;   end; {Initiare}
  procedure Print(var a:matrice);
    var i,j:byte;
      begin
        for i:=1 to n do begin
          for j:=1 to m do begin
            write(a[i,j],' '); end;
             writeln;
              end; {Print} end;
      function Free(i,j:integer):boolean;
          begin
           Free:=(a[i,j]=0) and (i<n) and (j<m);
          end;      {Free}
       procedure GO;
         begin
          i:=i+dx[robot.direction];
          j:=j+dy[robot.direction];
          b[i,j]:=b[i,j]+1;
         end;
          procedure Back;
         begin
          i:=i-dx[robot.direction];
          j:=j-dy[robot.direction];
          b[i,j]:=b[i,j]+1;
         end;
       procedure Right90;
         begin
          if robot.direction=3 then robot.direction:=-1;
           robot.direction:=robot.direction+1;
         end;
         procedure Left90;
         begin
          if robot.direction=0 then robot.direction:=4;
           robot.direction:=robot.direction-1;
         end;
Begin ClrScr; {Main Program}
Initiare;
Print(a);
readln;
Enter;
x:=i; y:=j;
robot.direction:=2;
  while Free(i,j) do
     Go;
    while flag=0 do  begin
     Right90;
      Go;
       if  a[i,j]=3 then flag:=1 else
         if not(Free(i,j))then begin
           Back;
            Left90;
             Go;
              if not(free(i,j))then begin
                Back;
                 Left90;
               end
           end
        end;

 Print(b);
readln;
  end.


  //File In.TXT
7 9
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 0 1
1 0 1 0 0 1 0 1 1
1 0 0 0 1 0 0 0 1
1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 1 0 1
1 2 1 1 1 1 1 3 1
// Matrix B
-1 1  0 -1  1  0  0 1 0 
 0 5  6  4  4  2  3 6 2 
 0 4  4  4  1 -1  2 4 0 
 0 3  2  1 -1  0  1 4 2 
 0 2 -1  0 -1  0 -1 2 1 
 0 2  0  0  0  0 -1 3 1 
 0 0 -1 -1 -1 -1 -1 2 0

Вот что получилось, робот находит выход, только он идёт по очень длиному пути.
Пробовал использовать матрицу B для генерации ответа ( надо пройти по минимальным числам ), но это не получилось...

Автор: -TarasBer- 30.03.2011 22:42

Так если ты хочешь кратчайший путь, то это тебе не правая рука нужна, а "обход в ширину" (в википедии поищи).

Автор: -TarasBer- 30.03.2011 22:44

> i:=i+dx[robot.direction];
j:=j+dy[robot.direction];

Вот нахрена я заводил поля robot.x и robot.y , если ты всё равно координаты хранишь в i, j?

Автор: DarkWishmaster 30.03.2011 22:53

Цитата(-TarasBer- @ 30.03.2011 18:44)

> i:=i+dx[robot.direction];
j:=j+dy[robot.direction];
Вот нахрена я заводил поля robot.x и robot.y , если ты всё равно координаты хранишь в i, j?

Мне просто так удобнее, не путаюсь )

Автор: -TarasBer- 30.03.2011 22:56

Через год ты проклянёшь себя при попытке понять, почему i,j - это координаты робота и для чего заведены поля x и y.

Автор: Lapp 1.04.2011 12:06

Нн-дя...
DarkWishmaster, ты извини, но ТАК программировать НЕЛЬЗЯ..
Я впервые вижу такое.. Возвращаемый результат процедуры - параметры цикла!! Где ты это почерпнул?? Я имею в виду сейчас, как ты находишь вход (процедура Enter). Давай разберем. По возрастанию важности ошибок:
1. Зачем делать процедурой кусок кода, который будет использован один раз?
2. Зачем проходить по масиву повторно? Ты мог сделать это при вводе.
3. Нельзя использовать значения параметров цикла вне цикла. Их значения не гарантируются.
4. Параметры цикла должны быть ЛОКАЛЬНЫМИ, то есть описаны внутри процедуры. Только ТР может пропустить такое, всякий нормальный современный компилятор выдаст ошибку.
5. При выполнении п.4 значения i и j будут недоступны в вызывающем модуле.
Я даже и не знаю, что тут еще добавить и какие рекомедации дать. Постарайся сделать выводы сам.
Так, пойду смотреть дальше..

Слушай, DarkWishmaster, ну я же просил тебя уже, кажется: пожалуйста, форматируй код! Ну это же не стихи, где ты можешь писать лесенкой, как тебе вздумается, под Маяковского. Процедура Print - энды пляшут танец с саблями что ли?

Ладно, с меня пока хватит. Я совершенно не понимаю, как можно ТАК УСЛОЖНИТЬ простейшую задачу. Вот тебе код - надеюсь, ты его разберешь. Заметь, что собственно решение занимает в нем 8 строк (в конце).

type
  tDir= array [0..3] of integer;

const
u: tDir = (-1,0,1,0);
v: tDir = (0,1,0,-1);

var
  maze: array of array of byte;
  d,d0,i,j,m,n,x,y,fx,fy: integer;
  s: string;
  f: text;

begin
  // reading the file
  Assign(f,'maze.dat');
  Reset(f);
  n:=0;
  while not EoF(f) do begin
    ReadLn(f,s);
    Inc(n)
  end;
  m:= Length(s);
  SetLength(maze,n+2,m+2);
  for i:=0 to n+1 do for j:=0 to m+1 do maze[i,j]:=1;
  Reset(f);
  for i:=1 to n do begin
    ReadLn(f,s);
    for j:=1 to m do begin
      case s[j] of
        '2': begin
          x:= i;
          y:= j;
        end;
        '3': begin
          fx:= i;
          fy:= j;
        end
      end;
      if s[j]<>'1' then maze[i,j]:= 0
    end
  end;
  Close(f);

  // printing a picture
  for i:=0 to n+1 do begin
    for j:=0 to m+1 do Write(maze[i,j]);
    WriteLn
  end;

  // passing the maze
  d:= 0;
  repeat
    d:=(d+1) mod 4;
    while maze[x+u[d],y+v[d]]<>0 do d:= (d+3) mod 4;
    Inc(x,u[d]);
    Inc(y,v[d]);
    WriteLn(x:4,y:4)
  until (x=fx) and (y=fy);
end.

Пример входного файла:

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

Автор: TarasBer 1.04.2011 12:50

> 1. Зачем делать процедурой кусок кода, который будет использован один раз?

Ну это-то как раз правильно.

Автор: Lapp 1.04.2011 14:17

Цитата(TarasBer @ 1.04.2011 9:50)

> 1. Зачем делать процедурой кусок кода, который будет использован один раз?

Ну это-то как раз правильно.

Ситуации, когда это оправдано, безусловно, бывают, и нередко. Но всегда полезно спросить (себя) - зачем? Так вот, в данном случае я не нахожу ответа на этот вопрос

. Достаточно было выделить этот кусок комментариями. Это не ошибка в прямом смысле слова. Тут это сыграло даже положительную роль. Как всегда, диалектика: не сделал бы он этого, никто бы сказал ему про остальные ошибки, и они бы остались надолго.. А сейчас, надеюсь, выводы будут сделаны

Автор: DarkWishmaster 1.04.2011 18:47

Спасибо, Lapp и TarasBer, буду исправляться по тихоньку.