Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.77/39: Рейтинг темы: голосов - 39, средняя оценка - 4.77
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
1

Лабиринт из массива

09.10.2008, 23:40. Показов 7738. Ответов 11
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вот есть такая задача:
Код
Лабиринт задан матрицей a(m,n), состоящей из 0 и 1, причем а[1,1]=0 и a[m,n]=0.
Разработать рекурсивную процедуру нахождения пути из клетки а[1,1] в a[m,n]. 
Путь должен состоять из элементов, равных 0.
Ходить можно только по вертикалям и горизонталям
Как я думал сначала использовать так называемое "правило правой(левой) руки" для прохождения лабиринта, но стал вопрос о том как например проверить стенку справа(слева) когда мы находимся на элементе A[1,1] (я иммею виду если "правой" мы считаем элемент A[0,1]-которой не существует) т.е. у нас там как-бы ничего нет, так с чего проверять?
Мне просто нужно допридумывать идею, проверку в начале, ну и ещё придумать что-бы это "начальная" проверка не мешала основной работе функции, т.к. мне надо через рекурсию писать, а это означает что придётся заново вызывать эту же функцию...Если у вас появились идеи отпишитесь плз, а то мне всё больше начинает казатся, что "правило правой(левой) руки" здесь плохо применимо и есть что-то ещё, попроще, а может быть и посложнее...
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.10.2008, 23:40
Ответы с готовыми решениями:

Игра лабиринт. ИИ в лабиринте. Как задать лабиринт
У меня есть следующее задание: Дано: - робот - лабиринт Задание: - Нужно реализовать...

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

3D лабиринт
мне надо смоделировать лаберинт для 3D игры на флеше(хотя бы кусочек). думаю конечно обратьться к...

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

11
0 / 0 / 0
Регистрация: 09.10.2008
Сообщений: 18
10.10.2008, 00:16 2
Это недоделаная программа подобного типа.
Сдесь стены лабиринта = 1 а проход 0 (как у тя ток наоборот )
посмотри код сам, я спать ппц хочу.
Программа не работает так как я ее не доделал. Но функции передвежения (Move) и проверки местоположения (Chek (не финишь ли это)) написаны вроде правильно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream.h>
#define R 6 
#define S 9 
struct Point
{
    int r,s;
};
int maze[R][S]={1,1,1,1,1,1,1,1,1, 
                1,0,0,0,1,0,0,0,1,
                1,1,1,0,0,0,1,1,1,
                1,1,1,0,0,0,1,1,1,
                1,0,0,0,0,0,0,0,1,
                1,1,1,1,1,1,1,1,1};
 
Point start, finish, way[54]; 
int k;  
void Check(Point *pcurr); 
void Move(Point *pcurr, int dr, int ds);
void main()
{
    Point curr;  
    start.r=2;   
    start.s=2;   //
    finish.r=5;  //   
    finish.s=8;  //
    curr=start;  //
    way[k]=curr;
    maze[curr.r][curr.s];
    Check(&curr);
    Move(&curr,1,0);//down
    Move(&curr,0,1);//->
    Move(&curr,-1,0);//<-
    Move(&curr,0,-1);//up
}
void Check(Point *pcurr)
{
    if (pcurr->r==finish.r && pcurr->s==finish.s)
    {
        cout<<"\nFinish!!1";
    }
}
 
void Move(Point *pcurr, int dr, int ds) 
{
    int cr,cs;
    cr=pcurr->r+dr;
    cs=pcurr->s+ds;
    if (cr<R && cs<S && maze[cr][cs]==0)
    {
        pcurr->s=cs;
        pcurr->r=cr;
        way[++k]=*pcurr;
        maze[cs][cr]=2;
        pcurr->s=cs-ds;
        pcurr->r=cr-dr;
        maze[cr][cs]=0;
        k--;
                      Check(&pcurr);
    }
}
0
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
10.10.2008, 00:22  [ТС] 3
Ну у меня как-бы и есть стены "1", а проход "0", ну и во 2-ых, я тока недавно начал изучать языки программирования и в C++ не шарю, да и как я вижу, у тебя проверки как-то не так проходят...у меня тут появилась мысль насчёт того что делать с
когда мы находимся на элементе A[1,1] (я иммею виду если "правой" мы считаем элемент A[0,1]-которой не существует) т.е. у нас там как-бы ничего нет
Я думаю как-бы "обрамит" основную матрицу введённую пользователем 1-ами, что-бы они там были, а начальную точку сместить на 1, т.е. не A[1,1], а A[1,2], хотя можно и массив с 0-ля начать, но проблема актуальна, я не могу придумать правильный алгоритм проверки...
0
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
12.10.2008, 22:32  [ТС] 4
Помогите закончить...
Код
Program laba11b;
type
 stil=array[0..100,0..100] of byte;
Var
 a:stil;
 i,j,m,n,b:integer;
Procedure lab(i,j:integer;b:integer);
begin
 If (i=m) and (j=n) then
  writeln('KoHeL/')
 else
 begin
  if b=1 then
  if a[i+1,j]=0 then  {!! BnpaBO !!}
  begin
   Writeln('---> A[' ,i+1, ',' ,j, ']');
   b:=1;
   lab(i+1,j,b);
  end;
   if a[i,j+1]=0 then {!! BnpaBO !!}
   begin
    Writeln('---> A[' ,i, ',' ,j+1, ']');
    b:=1;
    lab(i,j+1,b);
   end
  else
  b:=-1;
  if b=-1 then
  if a[i-1,j]=0 then  {!! BleBO !!}
  begin
   Writeln('----> A[' ,i-1, ',' ,j, ']');
   b:=-1;
   lab(i-1,j,b);
  end;
   if a[i,j+1]=0 then  {!! BleBO !!}
   begin
    Writeln('----> A[' ,i, ',' ,j+1, ']');
    b:=-1;
    lab(i,j+1,b);
   end
   else
   b:=0;
   if b=0 then
   if a[i,j-1]=0 then  {!! Bhu3 !!}
   begin
    Writeln('----> A[' ,i, ',' ,j-1, ']');
    b:=0;
    lab(i,j-1,b);
   end;
   if a[i+1,j]=0 then {!! Bhu3 !! }
   begin
    Writeln('----> A[' ,i+1, ',' ,j, ']');
    b:=0;
    lab(i+1,j,b);
   end
   else
   b:=2;
   if b=2 then
   if a[i,j+1]=0 then  {!! BBePx !!}
   begin
    Writeln('----> A[' ,i, ',' ,j-1, ']');
    b:=2;
    lab(i,j-1,b);
   end;
   if a[i-1,j]=0 then {!! BBePx !! }
   begin
    Writeln('----> A[' ,i+1, ',' ,j, ']');
    b:=2;
    lab(i+1,j,b);
   end
   else
   b:=1;
 end;
end;
begin
 Writeln('BBeDUte pa3MePHotb matPuL/bl mxn');
 Write('m=');
 readln(m);
 Write('n=');
 readln(n);
 for i:=1 to m do
  for j:=1 to n do
   begin
    Write('A[' ,i, ',' ,j, ']=');
    Readln(a[i,j]);
   end;
 for i:=0 to m+1 do
 begin
  a[i,0]:=1;
  a[i,n+1]:=1;
 end;
 for j:=1 to n+1 do
 begin
  a[0,j]:=1;
  a[m+1,j]:=1;
 end;
 for i:=0 to m+1 do
 begin
  Writeln;
  for j:=0 to n+1 do
   Write(a[i,j]);
 end;
 readln;
 b:=1;
 lab(1,1,b);
 Readln;
end.
Прога доходит до конца и пишет слово KoHeL/, но продолжает выполняться до переполнения стека, укажите ошибку, если не сложно.
0
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
12.10.2008, 23:20 5
Неправильно выход из рекурсии. Надо так:
Код
Procedure lab(i,j:integer;b:integer);
begin
 If (i=m) and (j=n) then
    begin
      writeln('KoHeL/');
      readln;
      halt;
    end
 else
и еще вот здесь вместо 1 надо 0
Код
for j:=[B][I][COLOR="Red"]1[/COLOR][/I][/B] to n+1 do
 begin
  a[0,j]:=1;
  a[m+1,j]:=1;
 end;
0
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
12.10.2008, 23:28  [ТС] 6
Спасибо за советы, но прога всё равно не работает, у меня иссякли мысли...
0
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
13.10.2008, 07:42 7
Сейчас потестировал программу, дело в том что она работает при n=m и при m>n. Когда столбцов больше чем строк, не работает. Проверьте сами, Вы скорее найдете ошибку. На всякий случай моя программа, которая на 2/3 работает.
Вложения
Тип файла: rar PROGA3.rar (662 байт, 126 просмотров)
0
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
14.10.2008, 03:44  [ТС] 8
Хотел бы вас поправить немного, программа не работает, когда происходят определённые повороты в лабиринте, все их описывать не вижу смысла, просто их не так много, сейчас переделываю программу полностью, уменьшая объём и дорабатывая её на ходу, надеюсь сегодня к утру, может быть завтра к вечеру закончу...
0
0 / 0 / 0
Регистрация: 23.10.2008
Сообщений: 6
23.10.2008, 20:28 9
Цитата Сообщение от lexus_ilia Посмотреть сообщение
Хотел бы вас поправить немного, программа не работает, когда происходят определённые повороты в лабиринте, все их описывать не вижу смысла, просто их не так много, сейчас переделываю программу полностью, уменьшая объём и дорабатывая её на ходу, надеюсь сегодня к утру, может быть завтра к вечеру закончу...
Всем привет!

Мне такую же задачу дали. Можете помочь с кодом и алгоритмом. написать нужно на С.
Я новичок. Спасибо!
0
10 / 10 / 2
Регистрация: 18.08.2008
Сообщений: 127
25.10.2008, 20:05 10
по борабану на каком языке писать .
надо составить новмальный алгоритм програму и все буде пучком.
1) 1- стена ; 0 - проход : 2- обрамляющая рамка лабиринта
если при анализе вылезит 2 - то это конец лабиринта- выход
2) анализировать надо не по правилу рук а про правилу часов
сначала свободна ли верхняя клетка . если не то правая ... нижняя левая .
разумется там надо учитывать был ли ты раньше в этой клетке .
0
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
25.10.2008, 20:29  [ТС] 11
Не полностью согласен, т.к. а если мы попали на перекрёсток?Ну что-то типа токого
Код
0001111
1101101
1000001
1011111
1000000
И если проверять так как вы предлогаете, то получается мы во время перекрёстка пойдём направо там наверх и зациклимся...
0
10 / 10 / 2
Регистрация: 18.08.2008
Сообщений: 127
26.10.2008, 20:51 12
не совсем !
первое что надо учитывать это вход на перекресток.
черепашка может двигаться в четырех направлениях
вверх , вправо , влево и вниз.
Так пусть есть переменная Dv (движение)и X,Y позиции. Dv будет равнo в зависимости от направления 1,2,3,4.
Теперь надо найти верное следующее направление Dv2. Возможных вариантов тоже будет 4 . нельзя не учитывать движение обратно . Там может быть карман ( апендекс). вычислять это движение разумеется тоже в определенном порядке .
если Dv=1 то Dv2= 2,3,4,1
Dv=2 то Dv2= 3,4,1.2
Dv=3 то Dv2= 4,1,2,3
Dv=4 то Dv2= 1,2,3,4
естественно
что бы облегчить код и анализ лучше ввести X1 и Y1 аналитические приращения
которые будут равны при Dv2=1 X1=0 Y1=-1
Dv2=1 X1=0 Y1=-1
Dv2=2 X1=1 Y1=0
Dv2=3 X1=0 Y1=1
Dv2=4 X1=-1 Y1=0

Теперь можно легко вычислить нужную клетку
то есть найти клетку равную 0 свободную в поле М
спросив М(X+X1,Y+Y2) если она равна нулю то сделать движение Dv=Dv2; X=X+X1;Y=Y+Y1
если это вход (=2) или выход(=3) то соответственно сделать выход из программы
если (=1) то это стенка Увеличить Dv2 на единицу .если Dv2=5 то сделать =1
кстати четвертое приращение Dv2 заставить черешку пятиться , а обратный ход свободен . Если же вы решили отмечать трассу(значением 4),то при анализе хода считать ,что это 0.
Еще данный алгоритм работает при ширине туннеля 1 или 2 .Еще шире не ручаюсь за результат .
Так как алгоритм анализирует соседние клетки (а они должны быть). то поле должно быть окружено границей из 1 или программно их поставив расширив размеры исходного поля на 2 .
0
26.10.2008, 20:51
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.10.2008, 20:51
Помогаю со студенческими работами здесь

Лабиринт
Вообщем у меня 2 проблемы: 1) Либирнт генерирует 2 раза 2) '8' ходит как хочит Поправте плз код...

Лабиринт с++
Есть код. только мне не понятен алгоритм который работает в bool PathExists(Labyrinth&amp; lab, int...

лабиринт
дан лабиринт размером NxN. форма лабиринта записана в тектовом файле. стена обозначается М. даны...

Лабиринт C++
я написал код лабиринта на c++, с помощью чего можно найти кратчайший путь выхода из лабиринта?...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru