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

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

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

Найдите маршрут в квадрате, который начинался бы и заканчивался в ячейке 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 - ето чорные квадратики .... Я написал програму но она работает исключительно для даной матрицы а вот как зделать болие универсальние ??? Может ест какието алгоритмы ???
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KEKCoGEN
Модератор
 Аватар для KEKCoGEN
1724 / 1602 / 388
Регистрация: 28.12.2010
Сообщений: 6,531
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
Модератор
 Аватар для KEKCoGEN
1724 / 1602 / 388
Регистрация: 28.12.2010
Сообщений: 6,531
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
Модератор
 Аватар для KEKCoGEN
1724 / 1602 / 388
Регистрация: 28.12.2010
Сообщений: 6,531
06.01.2011, 05:21     Прохождение лабиринта #7
Пройти все клетки один раз это однонаправленный граф...или как его там называют.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
Прохождение лабиринта C++
C++ Прохождение лабиринта

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

Или воспользуйтесь поиском по форуму:
KEKCoGEN
Модератор
 Аватар для KEKCoGEN
1724 / 1602 / 388
Регистрация: 28.12.2010
Сообщений: 6,531
23.02.2015, 01:24     Прохождение лабиринта #16
ЯрославК, лучше поздно чем никогда)
Yandex
Объявления
23.02.2015, 01:24     Прохождение лабиринта
Ответ Создать тему
Опции темы

Текущее время: 08:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru