Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
templier
0 / 0 / 0
Регистрация: 08.12.2014
Сообщений: 3
#1

Рекурсия (не могу из нее выйти) поиска пути в лабиринте - C++

08.12.2014, 08:54. Просмотров 565. Ответов 1
Метки нет (Все метки)

Добрый день, друзья!
Пытаюсь реализовать программу, которая бы находила путь в лабиринте(интовый массив, элемент =5 точка входа, элемент=6-точка выхода).
функция Generation вызывает рекурсивную функцию find_way. у меня проблема в том, что я не могу никак выйти из рекурсии. условие выхода- если сверху, слева, справа или снизу значение элемента == 6, то выход из функции,а также оно должно вернуть значение true, иначе false.
функция p смотрит, если ли рядом точка выхода.
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
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
bool p(int **maze,int x,int y)
        {
        if(maze[x+1][y]==6)
            {
                maze[x][y]=msum-1;return true;
            }else
            if( maze[x-1][y]==6)
            {
                maze[x][y]=msum-1;return true;
            }else
            if(maze[x][y+1]==6)
            {
                maze[x][y]=msum-1;return true;
            }else
            if(maze[x][y-1]==6)
            {
                maze[x][y]=msum-1;return true;
            }
            return false;
        }
 
 
 
 
        int find_way(int **maze,int x,int y,int n)
        {
            p(maze,x,y);
            bool f;
            f=p(maze,x,y);
            if(f)
            {
                for(int i=0;i<n+2;i++)
                for(int j=0;j<n+2;j++)
                {
                    if(maze[i][j]==-100) maze[i][j]=0;
                }
                return 1;
            }
            int z=1+ rand()%4;
                if(z==1)
                    if(x!=n+2-1)  //вниз
                    {
                        if(maze[x+1][y]==0 || maze[x+1][y]==6 )
                        {
                            if(maze[x+1][y]==6) return true;
                            else
                            {
                                maze[x][y]=maze[x+1][y];
                                maze[x][y]=msum-1;
                                msum=maze[x][y];
                                find_way(maze,x+1,y,n);
                            }
                        }
                    }
                if(z==2)
                    if(x!=0)//вверх
                    {
                        if(maze[x-1][y]==0 || maze[x-1][y]==6)
                        {
                            if(maze[x-1][y]==6) return true;
                            else
                            {
                                maze[x][y]=maze[x-1][y];
                                maze[x][y]=msum-1;
                                msum=maze[x][y];
                                find_way(maze,x-1,y,n);
                            }
                        }
                    }
                if(z==3)
                    if(y!=n+2-1)//вправо
                    {
                        if(maze[x][y+1]==0 || maze[x][y+1]==6)
                        {
                            if(maze[x][y+1]==6) return true;
                            else
                            {
                                maze[x][y]=maze[x][y+1];
                                maze[x][y]=msum-1;
                                msum=maze[x][y];
                                find_way(maze,x,y+1,n);
                            }
                        }
                    }
                if(z==4)
                    if(y!=0)//влево
                    {
                        if(maze[x][y-1]==0 || maze[x][y-1]==6)
                        {
                            if(maze[x][y-1]==6) return true;
                            else
                            {
                                maze[x][y]=maze[x][y-1];
                                maze[x][y]=msum-1;msum=maze[x][y];
                                find_way(maze,x,y-1,n);
                            }
                        }
                    }
            if(maze[x+1][y]==0 || maze[x-1][y]==0|| maze[x][y+1]==0 || maze[x][y-1]==0)
            find_way(maze,x,y,n);
 
        else
        {
            if(maze[x+1][y]==6)
            {
                maze[x][y]=msum=1;return true;
            }else
            if( maze[x-1][y]==6)
            {
                maze[x][y]=msum=1;return true;
            }else
            if(maze[x][y+1]==6)
            {
                maze[x][y]=msum=1;return true;
            }else
            if(maze[x][y-1]==6)
            {
                maze[x][y]=msum=1;return true;
            }else
            {
            //msum=msum+1;
 
                if(maze[x+1][y]==msum)
                {
                    maze[x][y]=-100;
                    msum=msum+1;
                    find_way(maze,x+1,y,n);
                }
                if(maze[x-1][y]==msum)
                {
                    maze[x][y]=-100;
                    msum=msum+1;
                    find_way(maze,x-1,y,n);
                }
                if(maze[x][y+1]==msum)
                {
                    maze[x][y]=-100;
                    msum=msum+1;
                    find_way(maze,x,y+1,n);
                }
                if(maze[x][y-1]==msum)
                {
                    maze[x][y]=-100;
                    msum=msum+1;
                    find_way(maze,x,y-1,n
                    );
                }
            }
        }
        }
 
    void Generation(int n,int obstacle)
        {
                    find_way(maze,1,1,n);
cout<<""Путь найден";
Путь находится, но она снова начинает его находить.
Помогите пожалуйста. Буду очень вам признателен
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2014, 08:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия (не могу из нее выйти) поиска пути в лабиринте (C++):

Алгоритм поиска пути в лабиринте, заданном связным графом - C++
использовать алгоритм поиска пути в лабиринте, заданном связным графом. граф уже задан в самой программе. Пример: int mas = {...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Рекурсия. Написать программу поиска минимального пути для произвольной пары городов - C++
Привет. Помогите пожалуйста решить задачку: Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с...

Поиск пути в лабиринте - C++
Есть двухмерный массив : 1 - препятствие, 0 - проход. Нужно найти кратчайший путь от одной точки до другой. У меня есть волновой...

Поиск пути в лабиринте - C++
Доброго времени суток! есть задача пройти лабиринт {1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1...

Рекурсия, вычислить площадь комнаты в квадратном лабиринте - C++
Требуется вычислить площадь комнаты в квадратном лабиринте. Формат входных данных В первой строке вводится число N – размер...

1
templier
0 / 0 / 0
Регистрация: 08.12.2014
Сообщений: 3
09.12.2014, 13:57  [ТС] #2
Товарищи программисты, помогите пожалуйста. Курсовая работа стоит на мертвой точке...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.12.2014, 13:57
Привет! Вот еще темы с ответами:

Поиск кратчайшего пути (рекурсия) - C++
Помогите пожалуйста. Пусть имеется n городов. Некоторые из них соединены дорогами известной длины. С помощью рекурсии найти Кратчайшие...

Не могу выйти из цикла - C++
Подскажите, пожалуйста, почему не выходит из цикла при вводе Y: do { cout &lt;&lt; &quot;Do you want to calculate again? (Y/N)&quot;; ...

Программа поиска пути в лабиринте - C++ Builder
Здравствуйте! Задали в универе написать программу на Билдере, которая бы искала путь в лабиринте. Лабиринт может задаваться как...

Алгоритм поиска пути в лабиринте - C (СИ)
159 ошибок помогите разобраться #include &quot;conio.h&quot; // Для функции getch() #include &lt;string.h&gt; struct screen_point{ // ...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.