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

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

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

Студворк — интернет-сервис помощи студентам
Вот есть такая задача:
Code
1
2
3
4
Лабиринт задан матрицей 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
09.10.2008, 23:40
Ответы с готовыми решениями:

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

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

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

11
0 / 0 / 0
Регистрация: 09.10.2008
Сообщений: 18
10.10.2008, 00:16
Это недоделаная программа подобного типа.
Сдесь стены лабиринта = 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
 Аватар для lexus_ilia
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
10.10.2008, 00:22  [ТС]
Ну у меня как-бы и есть стены "1", а проход "0", ну и во 2-ых, я тока недавно начал изучать языки программирования и в C++ не шарю, да и как я вижу, у тебя проверки как-то не так проходят...у меня тут появилась мысль насчёт того что делать с
когда мы находимся на элементе A[1,1] (я иммею виду если "правой" мы считаем элемент A[0,1]-которой не существует) т.е. у нас там как-бы ничего нет
Я думаю как-бы "обрамит" основную матрицу введённую пользователем 1-ами, что-бы они там были, а начальную точку сместить на 1, т.е. не A[1,1], а A[1,2], хотя можно и массив с 0-ля начать, но проблема актуальна, я не могу придумать правильный алгоритм проверки...
0
 Аватар для lexus_ilia
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
12.10.2008, 22:32  [ТС]
Помогите закончить...
Code
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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
Почетный модератор
 Аватар для Puporev
64314 / 47610 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
12.10.2008, 23:20
Неправильно выход из рекурсии. Надо так:
Pascal
1
2
3
4
5
6
7
8
9
Procedure lab(i,j:integer;b:integer);
begin
 If (i=m) and (j=n) then
    begin
      writeln('KoHeL/');
      readln;
      halt;
    end
 else
и еще вот здесь вместо 1 надо 0
Pascal
1
2
3
4
5
for j:=1 to n+1 do // <---
 begin
  a[0,j]:=1;
  a[m+1,j]:=1;
 end;
0
 Аватар для lexus_ilia
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
12.10.2008, 23:28  [ТС]
Спасибо за советы, но прога всё равно не работает, у меня иссякли мысли...
0
Почетный модератор
 Аватар для Puporev
64314 / 47610 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
13.10.2008, 07:42
Сейчас потестировал программу, дело в том что она работает при n=m и при m>n. Когда столбцов больше чем строк, не работает. Проверьте сами, Вы скорее найдете ошибку. На всякий случай моя программа, которая на 2/3 работает.
Вложения
Тип файла: rar PROGA3.rar (662 байт, 126 просмотров)
0
 Аватар для lexus_ilia
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
14.10.2008, 03:44  [ТС]
Хотел бы вас поправить немного, программа не работает, когда происходят определённые повороты в лабиринте, все их описывать не вижу смысла, просто их не так много, сейчас переделываю программу полностью, уменьшая объём и дорабатывая её на ходу, надеюсь сегодня к утру, может быть завтра к вечеру закончу...
0
0 / 0 / 0
Регистрация: 23.10.2008
Сообщений: 6
23.10.2008, 20:28
Цитата Сообщение от lexus_ilia Посмотреть сообщение
Хотел бы вас поправить немного, программа не работает, когда происходят определённые повороты в лабиринте, все их описывать не вижу смысла, просто их не так много, сейчас переделываю программу полностью, уменьшая объём и дорабатывая её на ходу, надеюсь сегодня к утру, может быть завтра к вечеру закончу...
Всем привет!

Мне такую же задачу дали. Можете помочь с кодом и алгоритмом. написать нужно на С.
Я новичок. Спасибо!
0
10 / 10 / 2
Регистрация: 18.08.2008
Сообщений: 127
25.10.2008, 20:05
по борабану на каком языке писать .
надо составить новмальный алгоритм програму и все буде пучком.
1) 1- стена ; 0 - проход : 2- обрамляющая рамка лабиринта
если при анализе вылезит 2 - то это конец лабиринта- выход
2) анализировать надо не по правилу рук а про правилу часов
сначала свободна ли верхняя клетка . если не то правая ... нижняя левая .
разумется там надо учитывать был ли ты раньше в этой клетке .
0
 Аватар для lexus_ilia
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
25.10.2008, 20:29  [ТС]
Не полностью согласен, т.к. а если мы попали на перекрёсток?Ну что-то типа токого
Code
1
2
3
4
5
0001111
1101101
1000001
1011111
1000000
И если проверять так как вы предлогаете, то получается мы во время перекрёстка пойдём направо там наверх и зациклимся...
0
10 / 10 / 2
Регистрация: 18.08.2008
Сообщений: 127
26.10.2008, 20:51
не совсем !
первое что надо учитывать это вход на перекресток.
черепашка может двигаться в четырех направлениях
вверх , вправо , влево и вниз.
Так пусть есть переменная 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
26.10.2008, 20:51
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru