Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
templier
0 / 0 / 1
Регистрация: 08.12.2014
Сообщений: 3
#1

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

08.12.2014, 08:54. Просмотров 641. Ответов 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++):

Алгоритм поиска пути в лабиринте, заданном связным графом
использовать алгоритм поиска пути в лабиринте, заданном связным графом. граф...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using...

Рекурсия. Написать программу поиска минимального пути для произвольной пары городов
Привет. Помогите пожалуйста решить задачку: Расстояния между городами заданы...

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

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

Рекурсия, вычислить площадь комнаты в квадратном лабиринте
Требуется вычислить площадь комнаты в квадратном лабиринте. Формат входных...

1
templier
0 / 0 / 1
Регистрация: 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
Привет! Вот еще темы с решениями:

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

Не могу выйти из цикла
Подскажите, пожалуйста, почему не выходит из цикла при вводе Y: do {...

Программа поиска пути в лабиринте
Здравствуйте! Задали в универе написать программу на Билдере, которая бы искала...

Алгоритм поиска пути в лабиринте
159 ошибок помогите разобраться #include &quot;conio.h&quot; // Для функции getch()...


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

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

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