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

@mstivuipadonok · Регистрация: 06.01.2011

Студворк — интернет-сервис помощи студентам

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

Найдите маршрут в квадрате, который начинался бы и заканчивался в ячейке 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 · 06.01.2011, 03:51

Решение задачи в использовании графов.

@Минич · 06.01.2011, 04:03

Сообщение от mstivuipadonok

Может ест какието алгоритмы ???

тут тема выхода из лабиринта, может чем поможет

@mstivuipadonok · 06.01.2011, 04:37 **[ТС]**

Уже придумал как решыть , но перебором и ето не найлутшый вариант (((( но работает

Сообщение от KEKCoGEN

Решение задачи в использовании графов.

можно поподробней ???

@KEKCoGEN · 06.01.2011, 04:53

http://hci.fenster.name/304y/lab6/
Так же полезно прочитать
http://ru.wikipedia.org/wiki/Поиск_в_ширину
и
http://ru.wikipedia.org/wiki/%... 0%BD%D1%83

@mstivuipadonok · 06.01.2011, 05:11 **[ТС]**

Спасибо , буду думать , найти выход я то мугу вся проблема в тому штоб пройти все клетки но буду пробовать через графы

@KEKCoGEN · 06.01.2011, 05:21

Пройти все клетки один раз это однонаправленный граф...или как его там называют.

valeriikozlov · 06.01.2011, 08:14

Сообщение от mstivuipadonok

Уже придумал как решыть , но перебором и ето не найлутшый вариант (((( но работает

Может покажете Ваш вариант перебором? Мы его посмотрим, может найдем как его улучшить.

@mstivuipadonok · 06.01.2011, 22:44 **[ТС]**

Вот код уже работает лутше , около минуты занимает обход , суть такова , значит 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 · 07.01.2011, 00:55

mstivuipadonok, Просмотрел я Ваш вариант. Перебор работает. Но у Вас не предусмотрено в коде если пути нет вообще. В этом случае программа вылетает. Переменная bkill в main() становится равной -1 и в WhatWay() идет обращение к несуществующему элементу point.

@mstivuipadonok · 07.01.2011, 16:44 **[ТС]**

Ага уже исправил , спасибо , но думаю дана тема может быть закрыта ))) всем спасибо

@Минич · 07.01.2011, 17:20

Вот еще один вариант: "перебор все возможных значений и вырисовывание первого найденного"!
Вариант поиска конечно не оптимален, некоторые варианты можно было бы на корню выкидывать, но как вариант пойдет:

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 · 08.01.2011, 16:05 **[ТС]**

Оууу вывод пройденого пути очень понравилса , у меня просто если всьо гуд , то пройденый путь нули , быстродействием правда уступает , но здесь минимальные поправки и будет супер , я вот посмотрел , и взависимости от размерности матрицы можно выберать разные алгоритмы , для 8Х8 хорош будет вправо , вниз , вверх , влево , тогда быстро проходит , но для не квадратных он не очень .... Спасибо за вариан , попробую в своем тоже чтобы путь выводило

@Минич · 08.01.2011, 21:28

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;
}

@ЯрославК · 22.02.2015, 20:56

Вводятся ширина и высота, лабиринт генерируется, и сам находит выход. Вам предлагается выбрать, просматривать, как ищется путь или нет.(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;
}

@KEKCoGEN · 23.02.2015, 01:24

ЯрославК, лучше поздно чем никогда)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@mstivuipadonok 0 / 0 / 0 Регистрация: 06.01.2011 Сообщений: 9

	Прохождение лабиринта 06.01.2011, 02:23. Показов 3493. Ответов 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 - ето чорные квадратики .... Я написал програму но она работает исключительно для даной матрицы а вот как зделать болие универсальние ??? Может ест какието алгоритмы ??? 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	06.01.2011, 03:51
	Решение задачи в использовании графов. 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	06.01.2011, 04:53
	http://hci.fenster.name/304y/lab6/ Так же полезно прочитать http://ru.wikipedia.org/wiki/Поиск_в_ширину и http://ru.wikipedia.org/wiki/%... 0%BD%D1%83 2

@mstivuipadonok 0 / 0 / 0 Регистрация: 06.01.2011 Сообщений: 9
	06.01.2011, 05:11 [ТС]
	Спасибо , буду думать , найти выход я то мугу вся проблема в тому штоб пройти все клетки но буду пробовать через графы 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	06.01.2011, 05:21
	Пройти все клетки один раз это однонаправленный граф...или как его там называют. 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	07.01.2011, 00:55
	mstivuipadonok, Просмотрел я Ваш вариант. Перебор работает. Но у Вас не предусмотрено в коде если пути нет вообще. В этом случае программа вылетает. Переменная bkill в main() становится равной -1 и в WhatWay() идет обращение к несуществующему элементу point. 1

@mstivuipadonok 0 / 0 / 0 Регистрация: 06.01.2011 Сообщений: 9
	07.01.2011, 16:44 [ТС]
	Ага уже исправил , спасибо , но думаю дана тема может быть закрыта ))) всем спасибо 0

@mstivuipadonok 0 / 0 / 0 Регистрация: 06.01.2011 Сообщений: 9
	08.01.2011, 16:05 [ТС]
	Оууу вывод пройденого пути очень понравилса , у меня просто если всьо гуд , то пройденый путь нули , быстродействием правда уступает , но здесь минимальные поправки и будет супер , я вот посмотрел , и взависимости от размерности матрицы можно выберать разные алгоритмы , для 8Х8 хорош будет вправо , вниз , вверх , влево , тогда быстро проходит , но для не квадратных он не очень .... Спасибо за вариан , попробую в своем тоже чтобы путь выводило 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	23.02.2015, 01:24
	ЯрославК, лучше поздно чем никогда) 0