Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 5.00
mstivuipadonok
0 / 0 / 0
Регистрация: 06.01.2011
Сообщений: 9
#1

Прохождение лабиринта - C++

06.01.2011, 02:23. Просмотров 1805. Ответов 15
Метки нет (Все метки)

Привет всем , вот такая задача ...

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

1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 2
0 0 0 2 2 0 0 0
2 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Дано такую матрицу 8X8 , 2 - ето чорные квадратики .... Я написал програму но она работает исключительно для даной матрицы а вот как зделать болие универсальние ??? Может ест какието алгоритмы ???
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2011, 02:23     Прохождение лабиринта
Посмотрите здесь:

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

Прохождение лабиринта - C++
Как написать программу для прохождения лабиринта? У меня не получается. Саму программу можно не писать, а только алгоритм дайте и советы....

Прохождение лабиринта - C++
Приведенная ниже сетка единиц и нулей - двумерный массив, представляющий лабиринт. 111111111111 100010000001 001010111101 ...

Прохождение лабиринта - C++
Нужно пройти от 1 до 16 самым коротким путем. И вывести на экран количество шагов.

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

Прохождение лабиринта со стеком - C++
Добрый вечер После запуска программа вылетает с ошибкой Stack Overflow и останавливается на внесение данных в стек (глядела на...

Прохождение лабиринта: неожиданное поведение программы (найти и исправить ошибки) - C++
Всем доброго времени суток. В общем написал я программу для генерации лабиринта и программу для его прохождения. В первой генерирую...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KEKCoGEN
Эксперт Java
1898 / 1776 / 432
Регистрация: 28.12.2010
Сообщений: 7,172
06.01.2011, 03:51     Прохождение лабиринта #2
Решение задачи в использовании графов.
Минич
66 / 66 / 3
Регистрация: 26.11.2010
Сообщений: 123
06.01.2011, 04:03     Прохождение лабиринта #3
Цитата Сообщение от mstivuipadonok Посмотреть сообщение
Может ест какието алгоритмы ???
тут тема выхода из лабиринта, может чем поможет
mstivuipadonok
0 / 0 / 0
Регистрация: 06.01.2011
Сообщений: 9
06.01.2011, 04:37  [ТС]     Прохождение лабиринта #4
Уже придумал как решыть , но перебором и ето не найлутшый вариант (((( но работает

Цитата Сообщение от KEKCoGEN Посмотреть сообщение
Решение задачи в использовании графов.
можно поподробней ???
KEKCoGEN
Эксперт Java
1898 / 1776 / 432
Регистрация: 28.12.2010
Сообщений: 7,172
06.01.2011, 04:53     Прохождение лабиринта #5
http://hci.fenster.name/304y/lab6/
Так же полезно прочитать
http://ru.wikipedia.org/wiki/Поиск_в_ширину
и
http://ru.wikipedia.org/wiki/%D0%9F%...B8%D0%BD%D1%83
mstivuipadonok
0 / 0 / 0
Регистрация: 06.01.2011
Сообщений: 9
06.01.2011, 05:11  [ТС]     Прохождение лабиринта #6
Спасибо , буду думать , найти выход я то мугу вся проблема в тому штоб пройти все клетки но буду пробовать через графы
KEKCoGEN
Эксперт Java
1898 / 1776 / 432
Регистрация: 28.12.2010
Сообщений: 7,172
06.01.2011, 05:21     Прохождение лабиринта #7
Пройти все клетки один раз это однонаправленный граф...или как его там называют.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 08:14     Прохождение лабиринта #8
Цитата Сообщение от mstivuipadonok Посмотреть сообщение
Уже придумал как решыть , но перебором и ето не найлутшый вариант (((( но работает
Может покажете Ваш вариант перебором? Мы его посмотрим, может найдем как его улучшить.
mstivuipadonok
0 / 0 / 0
Регистрация: 06.01.2011
Сообщений: 9
06.01.2011, 22:44  [ТС]     Прохождение лабиринта #9
Вот код уже работает лутше , около минуты занимает обход , суть такова , значит 4 ето куда можно ити , 0 уже ходили , 2 тупик .... короч сначчала я за схемой вправо пока не тупик , вниз пока не тупик , влево пока не тупик , вверх пока не тупик обхожу матрицу а потом если чо не то по каждей точки вертаюсь назад и смотрю куда ещо можно пойти , вот так то ))))

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include "stdafx.h"
 
typedef struct Point{
    int x;
    int y;
    int right;
    int down;
    int up;
    int left;
} POINTER;
 
int Step(int maxx,int maxy,int *x,int *y,int step_direction);
int Go(POINTER *point,int arr[100][100],int n,int m,int *x,int *y,int step,int killp);
int WhatWay(POINTER *point,int arr[100][100],int n,int m);
void SetPoint(POINTER *point,int x,int y);
 
int _tmain(int argc, _TCHAR* argv[])
{
    int n,m,arr[100][100],i,j,x=0,y=0;
    int kill,way,elements,bkill,kill2;
    POINTER point[100];
    n=8;m=8;
    elements=n*m-7;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            arr[i][j]=4;
 
    arr[3][6]=arr[3][7]=arr[4][3]=arr[4][4]=arr[5][0]=arr[5][1]=2;
    printf("First Matrix\n\n"); 
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)
            printf("%d ",arr[i][j]);
    printf("\n");
    }
    
    printf("\nWait several minutes, followed data processing ... \n "); 
    kill=Go(point,arr,n,m,&x,&y,1,0);
    bkill=kill-1;
    
    if(kill!=elements){
        while(1){
        
 
        way=WhatWay(point+bkill,arr,n,m);
        if(way==0) {
    
            arr[point[bkill].x][point[bkill].y]=4;
            point[bkill].down=point[bkill].left=point[bkill].right=point[bkill].up=0;
            bkill--;
        }
    
        else {
            x=point[bkill].x;y=point[bkill].y;
            kill2=Go(point,arr,n,m,&x,&y,way,bkill);
            bkill=bkill+kill2-1;
            if(bkill==elements&&x==1&&y==0) break;
        }
        }
    }
 
        
        
    printf("Matrix after passage \n");  
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)
            printf("%d ",arr[i][j]);
    printf("\n");
    }
    return 0;
 
 
}
 
 
int Step(int maxx,int maxy,int *x,int *y,int step_direction){
    int xpr=*x,ypr=*y;
    
    switch (step_direction){
        case 1:     ypr++;
                    if(ypr<maxy){
                       *y=ypr;
                        return 1;
                    }
                    else return 0;
        case 2:     xpr++;
                    if(xpr<maxx){
                       *x=xpr;
                        return 1;
                    }
                    else return 0;
        case 4:     xpr--;
                    if(xpr>=0){
                       *x=xpr;
                        return 1;
                    }
                    else return 0;
        case 3:     ypr--;
                    if(ypr>=0){
                       *y=ypr;
                        return 1;
                    }
                    else return 0;
   }
 
}
 
void SetPoint(POINTER *point,int x,int y){
    point->x=x;
    point->y=y;
}
 
int Go(POINTER *point,int arr[100][100],int n,int m,int *x,int *y,int step,int kpoint){
int i=0,st,X,Y;
int killp=1;
SetPoint(point+kpoint,*x,*y);
X=*x;Y=*y;
while(1){
    
    if(step==1){
        st=Step(n,m,x,y,step);
            if(arr[*x][*y]==2) st=0;
            if(arr[*x][*y]==0) st=0;
            if(st==1){
                i=0;X=*x;Y=*y;
                arr[(point+kpoint)->x][(point+kpoint)->y]=0;
                (point+kpoint)->right=1;
                killp++;
                kpoint++;
                 SetPoint(point+kpoint,*x,*y);  
            }
            if(st==0){
                *x=X; *y=Y;
                step=2;
            }
    }
    if(step==2){
        st=Step(n,m,x,y,step);
            if(arr[*x][*y]==2) st=0;
            if(arr[*x][*y]==0) st=0;
            if(st==1){
                i=0;X=*x;Y=*y;
                arr[(point+kpoint)->x][(point+kpoint)->y]=0;
                (point+kpoint)->down=1;
                killp++;
            
                 kpoint++;
                 SetPoint(point+kpoint,*x,*y);  
            }
            if(st==0){
                *x=X; *y=Y;
                step=3;
            }
    }
    if(step==3){
        st=Step(n,m,x,y,step);
            if(arr[*x][*y]==2) st=0;
            if(arr[*x][*y]==0) st=0;
            if(st==1){
                i=0;X=*x;Y=*y;
                arr[(point+kpoint)->x][(point+kpoint)->y]=0;
                (point+kpoint)->left=1;
                killp++;
            
                 kpoint++;
                 SetPoint(point+kpoint,*x,*y);  
            }
            if(st==0){
                *x=X; *y=Y;
                step=4;
            }
    }
    if(step==4){
        st=Step(n,m,x,y,step);
            if(arr[*x][*y]==2) st=0;
            if(arr[*x][*y]==0) st=0;
            if(st==1){
                i=0;X=*x;Y=*y;
                arr[(point+kpoint)->x][(point+kpoint)->y]=0;
                (point+kpoint)->up=1;
                killp++;
            
                 kpoint++;
                 SetPoint(point+kpoint,*x,*y);  
            }
            if(st==0){
                *x=X; *y=Y;
                step=1;
            }
    }
 
    i++;
    if(i==3) break;
 
}
arr[(point+kpoint)->x][(point+kpoint)->y]=0;
return killp;
}
 
int WhatWay(POINTER *point,int arr[100][100],int n,int m){
    
        if(arr[(point->x)][(point->y)+1]==4&&point->right!=1){ 
            point->right=1;
            if(point->left!=1)point->left=0;
            if(point->up!=1)point->up=0;
            if(point->down!=1)point->down=0;
            return 1;
        }
        if(arr[(point->x)+1][point->y]==4&&point->down!=1){ 
            point->down=1;
            if(point->left!=1)point->left=0;
            if(point->up!=1)point->up=0;
            if(point->right!=1)point->right=0;
            return 2;
        }
        if(arr[(point->x)-1][point->y]==4&&point->up!=1){ 
            point->up=1;
            if(point->left!=1)point->left=0;
            if(point->down!=1)point->down=0;
            if(point->right!=1)point->right=0;
            return 4;
        }
        if(arr[point->x][(point->y)-1]==4&&point->left!=1){ 
            point->left=1;
            if(point->down!=1)point->down=0;
            if(point->up!=1)point->up=0;
            if(point->right!=1)point->right=0;
            return 3;
        }
            if(point->left!=1)point->left=0;
            if(point->down!=1)point->down=0;
            if(point->up!=1)point->up=0;
            if(point->right!=1)point->right=0;
            return 0;
        
        
        
}
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.01.2011, 00:55     Прохождение лабиринта #10
mstivuipadonok, Просмотрел я Ваш вариант. Перебор работает. Но у Вас не предусмотрено в коде если пути нет вообще. В этом случае программа вылетает. Переменная bkill в main() становится равной -1 и в WhatWay() идет обращение к несуществующему элементу point.
mstivuipadonok
0 / 0 / 0
Регистрация: 06.01.2011
Сообщений: 9
07.01.2011, 16:44  [ТС]     Прохождение лабиринта #11
Ага уже исправил , спасибо , но думаю дана тема может быть закрыта ))) всем спасибо
Минич
66 / 66 / 3
Регистрация: 26.11.2010
Сообщений: 123
07.01.2011, 17:20     Прохождение лабиринта #12
Вот еще один вариант: "перебор все возможных значений и вырисовывание первого найденного"!
Вариант поиска конечно не оптимален, некоторые варианты можно было бы на корню выкидывать, но как вариант пойдет:
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
156
157
158
#include <iostream>
#include <iomanip>
 
using namespace std;
/*
const int N = 8;
int arr[N][N] = { {1,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,2,2},
                  {0,0,0,2,2,0,0,0},
                  {2,2,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0} };
//*/
//*
const int N = 4;
int arr[N][N] = { {1,0,0,0},
                  {0,0,2,0},
                  {0,0,2,0},
                  {0,0,0,0} };
//*/
struct CFind {
    int x,
        y,
        value;
    CFind *nextTop,
          *nextLeft,
          *nextBelow,
          *nextRight,
          *last;
    CFind(int _x, int _y, int _v): x(_x), y(_y), value(_v), nextTop(NULL), nextLeft(NULL), nextBelow(NULL), nextRight(NULL), last(NULL) {}
};
 
CFind* find(CFind *, int);
bool verification(CFind *);
void outputWay(CFind *);
 
void main()
{
    setlocale(LC_ALL, "Russian");   
    
    int s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (arr[i][j] == 2)
                s++;
 
 
    CFind *f = new CFind(0, 0, 1);  // начальная точка
    f = find(f, s);
 
    if (f)
        outputWay(f);       
    else {
        system("cls");
        cout << "Не имеет варианта!!!" << endl;
    }
 
    system("pause");
}
 
CFind* find(CFind *f, int s)
{
    CFind *temp;
    if (f->x - 1 >= 0) { // вверх
        temp = new CFind(f->x - 1, f->y, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s)
            return f;
        if (verification(temp))
            delete temp;
        else {
            f->nextTop = temp;
            outputWay(f);
            temp = find(f->nextTop, s);
            if (temp) return temp;
            else delete temp;
        }
    }
    if (f->y - 1 >= 0) { // влево
        temp = new CFind(f->x, f->y - 1, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s)
            return f;
        if (verification(temp))
            delete temp;
        else {
            f->nextLeft = temp;
            outputWay(f);
            temp = find(f->nextLeft, s);
            if (temp) 
                return temp;
            else delete temp;
        }
    }
    if (f->x + 1 < N) { // вниз
        temp = new CFind(f->x + 1, f->y, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s)
            return f;
        if (verification(temp))
            delete temp;
        else {
            f->nextBelow = temp;
            outputWay(f);
            temp = find(f->nextBelow, s);
            if (temp) return temp;
            else delete temp;
        }
    }
    if (f->y + 1 < N) { // вправо
        temp = new CFind(f->x, f->y + 1, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s)
            return f;
        if (verification(temp))
            delete temp;
        else {
            f->nextRight = temp;
            outputWay(f);
            temp = find(f->nextRight, s);
            if (temp) return temp;
            else delete temp;
        }
    }
    return NULL;
}
 
bool verification(CFind *f)
{
    int x = f->x,
        y = f->y;
    while (f->last) {
        if (x == f->last->x && y == f->last->y ||
             arr[f->last->x][f->last->y] == 2)
            return true;
        f = f->last;
    }
    return false;
}
 
void outputWay(CFind *f)
{
    int a[N][N] = {{0}};
 
    while (f) {
        a[f->x][f->y] = f->value;
        f = f->last;
    }
    system("cls");
    cout << "Путь прохождения:" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << setw(3) << a[i][j];
        cout << endl;
    }
}
До конца не решена проблема утечки памяти! Может у кого какие предположения будут!!!
mstivuipadonok
0 / 0 / 0
Регистрация: 06.01.2011
Сообщений: 9
08.01.2011, 16:05  [ТС]     Прохождение лабиринта #13
Оууу вывод пройденого пути очень понравилса , у меня просто если всьо гуд , то пройденый путь нули , быстродействием правда уступает , но здесь минимальные поправки и будет супер , я вот посмотрел , и взависимости от размерности матрицы можно выберать разные алгоритмы , для 8Х8 хорош будет вправо , вниз , вверх , влево , тогда быстро проходит , но для не квадратных он не очень .... Спасибо за вариан , попробую в своем тоже чтобы путь выводило
Минич
66 / 66 / 3
Регистрация: 26.11.2010
Сообщений: 123
08.01.2011, 21:28     Прохождение лабиринта #14
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <iostream>
#include <iomanip>
 
using namespace std;
 
#ifndef _DEBUG
const int N = 8;
int arr[N][N] = { {1,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,2,2},
                  {0,0,0,2,2,0,0,0},
                  {2,2,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0},
                  {0,0,0,0,0,0,0,0} };
#endif
 
#ifdef _DEBUG
const int N = 4;
int arr[N][N] = { {1,0,0,0},
                  {0,0,2,0},
                  {0,0,2,0},
                  {0,0,0,0} };
#endif
 
struct CFind {
    int x,
        y,
        value;
    CFind *nextTop,
          *nextLeft,
          *nextBelow,
          *nextRight,
          *last;
    CFind(int _x, int _y, int _v): x(_x), y(_y), value(_v), nextTop(NULL), nextLeft(NULL), nextBelow(NULL), nextRight(NULL), last(NULL) {}
    ~CFind() {
        delete nextTop;
        delete nextLeft;
        delete nextBelow;
        delete nextRight;
    }
};
 
CFind* find(CFind *, int);
bool verification(CFind *);
void outputWay(CFind *);
 
void main()
{
    setlocale(LC_ALL, "Russian");
    clock_t startTime = clock();
    int time, h, m, s;
 
    int sum = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (arr[i][j] == 2)
                sum++;
 
 
    CFind *f = new CFind(0, 0, 1);  // начальная точка
    f = find(f, sum);
 
    if (f)
        outputWay(f);       
    else {
        system("cls");
        cout << "Не имеет варианта!!!" << endl;
    }
 
    delete f;
 
    time = (clock() - startTime) / CLOCKS_PER_SEC;
    s = time % 60;
    m = ((time - s) % 3600) / 60;
    h = (time - m - s) / 3600;
    cout << endl << "Время: ";
    if (h) cout << h << "ч ";
    if (m) cout << m << "м ";
    if (s) cout << s << "с";
    cout << endl;
 
    system("pause");
}
 
CFind* find(CFind *f, int s)
{
    CFind *temp;
    if (f->x - 1 >= 0) { // вверх
        temp = new CFind(f->x - 1, f->y, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s) {
            delete temp;
            return f;
        }
        if (verification(temp)) {
            delete temp;
        } else {
            f->nextTop = temp;
#ifdef _DEBUG
            outputWay(f);
#endif
            temp = find(f->nextTop, s);
            if (temp) return temp;
            else {
                delete f->nextTop;
                f->nextTop = NULL;
                delete temp;
            }
        }
    }
    if (f->y - 1 >= 0) { // влево
        temp = new CFind(f->x, f->y - 1, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s) {
            delete temp;
            return f;
        }
        if (verification(temp)) {
            delete temp;
        } else {
            f->nextLeft = temp;
#ifdef _DEBUG
            outputWay(f);
#endif
            temp = find(f->nextLeft, s);
            if (temp) return temp;
            else {
                delete f->nextLeft;
                f->nextLeft = NULL;
                delete temp;
            }
        }
    }
    if (f->x + 1 < N) { // вниз
        temp = new CFind(f->x + 1, f->y, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s) {
            delete temp;
            return f;
        }
        if (verification(temp)) {
            delete temp;
        } else {
            f->nextBelow = temp;
#ifdef _DEBUG
            outputWay(f);
#endif
            temp = find(f->nextBelow, s);
            if (temp) return temp;
            else {
                delete f->nextBelow;
                f->nextBelow = NULL;
                delete temp;
            }
        }
    }
    if (f->y + 1 < N) { // вправо
        temp = new CFind(f->x, f->y + 1, f->value + 1);
        temp->last = f;
        if (arr[temp->x][temp->y] == 1 && f->value == N * N - s) {
            delete temp;
            return f;
        }
        if (verification(temp)) {
            delete temp;
        } else {
            f->nextRight = temp;
#ifdef _DEBUG
            outputWay(f);
#endif
            temp = find(f->nextRight, s);
            if (temp) return temp;
            else {
                delete f->nextRight;
                f->nextRight = NULL;
                delete temp;
            }
        }
    }
    return NULL;
}
 
bool verification(CFind *f)
{
    int x = f->x,
        y = f->y;
    while (f->last) {
        if (x == f->last->x && y == f->last->y ||
             arr[f->last->x][f->last->y] == 2)
            return true;
        f = f->last;
    }
    return false;
}
 
void outputWay(CFind *f)
{
    int a[N][N] = {{0}};
    
    while (f) {
        a[f->x][f->y] = f->value;
        f = f->last;
    }
    system("cls");
    cout << "Путь прохождения:" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << setw(3) << a[i][j];
        cout << endl;
    }
}
Вот решена часть проблемы с утечкой памяти, но к завершению программы чертова дюжина объектов все таки не удаляются (теряются). Но что хорошо выделенная память уже не растет.
После построения Release и запуска EXE-шника, а не из Visual Studio, у меня ответ в 8-разрядной находится за 5 минут. (Кстати, при отладке (Debug) будет работать с 4-разрядная матрица, а при построении Release, 8-разрядная).
В предыдущей моей версии много накладных расходов приходилось на отображение процесса поиска пути. В этой же версии отображение работает только для отладки (Debug).

Может есть у кого какие идеи, где память не освобождается?! Чужой глаз быстрей найдет чем свой!!!(Эксперты ну хде вы?!)

Добавлено через 4 часа 35 минут
Проблема с утечкой памяти полностью решена!!!
Для ее устранения требуется удалить деструктор структуры (за не необходимостью и вызова ошибки с ним) и добавить следующий код в главную функцию (main()) между блоком вывода результата и вычислением времени.
C++
1
2
3
4
5
6
CFind *temp;
while (f) {
    temp = f;
    f = f->last;
    delete temp;
}
ЯрославК
2 / 2 / 0
Регистрация: 22.02.2015
Сообщений: 10
22.02.2015, 20:56     Прохождение лабиринта #15
Вводятся ширина и высота, лабиринт генерируется, и сам находит выход. Вам предлагается выбрать, просматривать, как ищется путь или нет.(yes/no). Удачи
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
156
157
158
159
160
161
162
163
164
165
166
#include <iostream>
#include <math.h>
#include <cmath>
#include <string>
#include <ctime>
#include <windows.h> 
#include <stdio.h>
using namespace std;
int main(){
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, (WORD)((0 << 4) | 11));
    setlocale(0, "rus");
    srand(time(0));
    string b[1000],t="p";
    int a = 1, c[1000], c1 = 2, n, k = 0,ii=0,oo=0;
    while (ii % 2 == 0 || oo % 2 == 0 || ii < 5 || oo < 5 || (ii + 2)*(oo + 2) >= 1000 || oo>70){
        cout << "Введите нечетную высоту,ширену, рекомендовано 15 27." << endl << "Самая жесть 23 37: ";
        cin >> ii >> oo;
        if (ii < 5) cout << "Маленикая высота!!!" << endl;
        if (oo < 5) cout << "Маленикая ширина!!!" << endl;
        if ((ii + 2)*(oo + 2) >= 1000) cout << "Слишком большой лабиринт" << endl;
        if (oo>70)cout << "Слишком большая ширина" << endl;
        if (oo % 2 == 0 || ii % 2 == 0)cout << "Числа должны быть нечетными!!" << endl;
    }
    ii += 2;
    oo += 2;
    for (int x = 0; x < ii*oo; x++){
        b[x] = " ";
        if (x < oo)b[x] = "#";
        if (x>ii*oo-oo-1)b[x] = "#";
        if (x % oo == 0)b[x] = "#";
        if (x % oo == oo-1)b[x] = "#";
    }
    while (a%2==1)
       a = rand() % (oo-4)+oo*ii-oo+2;
    b[a] = ".";
    b[a-oo] = ".";
    a = 1;
    while (a%2==1)
       a = rand() % (oo-4)+2;
    b[a] = ".";
    b[a+oo] = ".";
    a += oo*2;
    cout << 1;
    while (c1>1){
        int a1 = a;
        if (k < 15){
            c[c1] = a;
            c1++;
        }
        b[a] = ".";
        k = 0;
        while (a1 == a && k<15){
            n = rand() % 4 + 1;
            if (n == 1 && b[a + 2] ==" ")a++;
            if (n == 2 && b[a + oo*2] ==" ")a += oo;
            if (n == 3 && b[a - oo*2] ==" " )a -= oo;
            if (n == 4 && b[a - 2] ==" ")a--;
            k++;
        }
        if (k == 15){
            c[c1 - 1] = 0;
            c1 -= 2;
            a = c[c1];
            c1++;
        }
        if (a>0)
            b[a] = ".";
        if (a < 0)
            c1 = 0;
        if (k < 15){
            if (n == 1)a++;
            if (n == 2)a += oo;
            if (n == 3)a -= oo;
            if (n == 4)a--;
            b[a] = ".";
        }
    }
    b[oo*2] = "#";
    for (int x = 0; x < oo*ii; x++){
        if (b[x] == "#")b[x] = "";
        if (b[x] == " ")b[x] = "#";
        if (x>oo * 2||x<oo)
             if (b[x] == ".")b[x] = " ";
    }
    system("CLS");
    for (int x = 0; x < oo*ii; x++){
        cout << b[x];
        if (x % oo == oo-1)
            cout << endl;
    }
    //Прохождение
    int a1,a2,m[1000],j,h=0;
    c1 = 0;
    cout << "Хотите следить за прохождением лабиринта? ";
    while (h==0){
        cin >> t;
        if (t == "yes"){
            h = 1;
            j = 0;
        }
        if (t == "no"){
            h = 1;
            j = 1;
        }
    }
    k = j;
    for (int x = 0; x < oo; x++){
        for (int y = 0; y < oo*ii; y++)
            b[y] = b[y + 1];
    }
    for (int x = 0; x < oo;x++)
        if (b[x] == ".")
            a = x;
    for (int x = oo*(ii-3)-1; x < oo*(ii-2); x++)
        if (b[x] == " ")
            a1 = x;
    for (int x = 0; x < 1000; x++)
        c[x] = 0;
       b[a] = ".";
    while (a != a1){
        if (k == 0){
            system("CLS");
            for (int x = 0; x < oo*ii; x++){
                cout << b[x];
                if (x % oo == oo - 1)
                    cout << endl;
            }
            Sleep(150);
        }
        n = 0;
        a2 = a;
        while (a2 == a){
            n++;
            k = j;
            if (n == 1 && b[a - oo] ==" "&&a - oo>0&&m[a-oo]!=666)a -= oo;
            if (n == 2 && b[a - 1] == " "&&m[a -1] != 666)a--;
            if (n == 3 && b[a + 1] == " "&&m[a +1] != 666)a++;
            if (n == 4 && b[a + oo] == " "&&m[a + oo] != 666)a += oo;
            if (n == 5){
                k = 1;
                n = 0;
                c1--;
                b[a] = " ";
                m[a] = 666;
                c1--;
                a = c[c1];
                c1++;
            }
        }
        b[a] = ".";
        c[c1] = a;
        c1++;
    
    }
    system("CLS");
    for (int x = 0; x < oo*ii; x++){
        if (b[x] == ".")
            SetConsoleTextAttribute(hConsole, (WORD)((0 << 4) | 14));
        cout << b[x];
        if (x % oo == oo - 1)
            cout << endl;
        SetConsoleTextAttribute(hConsole, (WORD)((0 << 4) | 11));
    }
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2015, 01:24     Прохождение лабиринта
Еще ссылки по теме:

Задача на прохождение пути - C++
Некий мужчина отправляется на работу, которая находится на расстоянии 100 км от дома. Дойдя до места работы, он вдруг вспоминает, что перед...

Зацикливается прохождение по лабиринту - C++
Суть задачи: даны матрица NxM, даны 2 точки точка входа в лабиринт и выхода(пока отрубил,беру поиск с верхней точки), необходимо пройтись...

Поперечное прохождение бинарного дерева - C++
Собственно вопрос такой. В каком порядке при этом происходит обход бинарного дерева и как это может быть реализовано. Про обратный,...

Работа с линейными массивами. Заполнение и прохождение по массиву. - C++
Сформировать второй одномерный массив и заполнить его квадратными корнями от элементов первого. Написать в коде С++ Зарание спасибо

нахождение времени, потраченного на прохождение путником половины пути - C++
помгите найти ошибку, по чему программа не правильно считает условие Путник двигался t1 часов со скоростью v1 км/ч, затем t2 часов — со...


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

Или воспользуйтесь поиском по форуму:
KEKCoGEN
Эксперт Java
1898 / 1776 / 432
Регистрация: 28.12.2010
Сообщений: 7,172
23.02.2015, 01:24     Прохождение лабиринта #16
ЯрославК, лучше поздно чем никогда)
Yandex
Объявления
23.02.2015, 01:24     Прохождение лабиринта
Ответ Создать тему
Опции темы

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