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

Создать программу, отыскивающую проход по лабиринту - C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
26.06.2013, 12:35     Создать программу, отыскивающую проход по лабиринту #1
Создать программу, отыскивающую проход по лабиринту.
Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице.
Программа находит проход через лабиринт, двигаясь от заданного входа. После отыскания прохода программа выводит найденный путь в виде координат квадратов. Для хранения пути использовать стек.

Программа должна работать примерно так:
Берем любую точку и осматриваем ее окрестность, находим открытый квадрат и кладем точку входа в стек . дальше смотрим окрестности текущей точки если они закрыты, то вытаскиваем предыдущую из стека и смотрим на "проходимость" оставшихся сторон окрестности.
Сама матрица задается в коде, т.е. не рандомная.
Пример:

0 1 1
0 0 0
1 1 0

Должно вывести координаты: (1,1);(1,2);(2,2);(2,3);(3,3)

Знаю заезженная тема, есть куча постов об этом на форуме, в других сайтах и методичках, но ничего толкового я, к сожалению, не нашел. Помогите, пожалуйста, с реализацией...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5534 / 2568 / 234
Регистрация: 01.11.2011
Сообщений: 6,345
Завершенные тесты: 1
26.06.2013, 13:19     Создать программу, отыскивающую проход по лабиринту #2
@ololoshka(, очень хорошая тема. Попробуйте сначала самостоятельно додуматься.
Ну а так вот статья даже с псевдокодами. Ознакомьтесь.
Так же есть так называемое правило случайной руки - для нахождения пути в лабиринте без возможности возврата.

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

Какие у вас мысли по поводу вашей задачи?
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
26.06.2013, 13:23     Создать программу, отыскивающую проход по лабиринту #3
Цитата Сообщение от SatanaXIII Посмотреть сообщение
@ololoshka(, очень хорошая тема. Попробуйте сначала самостоятельно додуматься.
Ну а так вот статья даже с псевдокодами. Ознакомьтесь.
Так же есть так называемое правило случайной руки - для нахождения пути в лабиринте без возможности возврата.

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

Какие у вас мысли по поводу вашей задачи?
граф невзвешанный тут и DFS с BFS'ом подойдут.
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
26.06.2013, 14:06  [ТС]     Создать программу, отыскивающую проход по лабиринту #4
Цитата Сообщение от SatanaXIII Посмотреть сообщение
@ololoshka(, очень хорошая тема. Попробуйте сначала самостоятельно додуматься.
Ну а так вот статья даже с псевдокодами. Ознакомьтесь.
Так же есть так называемое правило случайной руки - для нахождения пути в лабиринте без возможности возврата.

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

Какие у вас мысли по поводу вашей задачи?
Есть сырой код, просто рекурсия с копированием подпутей, выводит все возможные не пересекающиеся пути. Но реализовать код с помощью стека не могу.
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
#include <iostream>
using namespace std;
 
 
int mas[3][3]={
  0,1,1
 ,0,0,0
 ,1,1,0};
 
int X=3, Y=3, x=0, y=0;//X и Y - координаты конца, x и y координаты начала
 
int Make(int x, int y, char s[1000])
{
    char st[1000];
    strcpy(st,s);
    sprintf (st, "%s[%d,%d] -> ", st, x, y);
    if (x==X && y==Y)
         {
        printf("%s\n\n",st);
        return 0;
         }
    
    if (x > 0) 
    if (mas[x - 1][y] == 0) 
          {
          mas[x][y]+=3;              // +=3/-=3 -  запирает/отпирает клетки при итерациях
          Make(x-1, y, st); 
          mas[x][y]-=3;              
          }
    if (x < 9) 
    if (mas[x + 1][y] == 0) 
          {
          mas[x][y]+=3; 
          Make(x+1, y, st); 
          mas[x][y]-=3;
          }
    if (y > 0) 
    if (mas[x][y - 1] == 0) 
          {
                 mas[x][y]+=3;
                 Make(x, y-1, st);
                 mas[x][y]-=3;
          }
    if (y < 9) 
    if (mas[x][y + 1] == 0) 
          {
                 mas[x][y]+=3;
                 Make(x, y+1, st); 
                 mas[x][y]-=3;}
          }
 
int main()
{
    Make(x, y, "");
    system("pause");
    return 0;
}
Мимино
 Аватар для Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
26.06.2013, 14:13     Создать программу, отыскивающую проход по лабиринту #5
Делала когда то что то подобное. Без стека, конечно, но может найдете что полезное.
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
#include "stdafx.h"
#include <iostream>
#include <windows.h>
using namespace std;
 
bool mazeTraverse(char [][13], int, int);
 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    const int size = 13;
    char lab[size - 1][size] = {"############",
                            "#...#......#",
                            "#.#.#.####.#",
                            "###.#....#.#",
                            "#....###.#..",
                            "####.#.#.#.#",
                            "#..#.#.#.#.#",
                            "##.#.#.#.#.#",
                            "#........#.#",
                            "######.###.#",
                            "#......#...#",
                            "############"};
    int a, b;
 
    for (int i = 0; i < size - 1; i++)
        cout << lab[i] << endl;
 
    do
    {
        cout << endl << "Введите стартовые координаты через пробел: ";
        cin >> a >> b;
 
        if (lab[a][b] != '#')
            break;
        else
            cout << "Вы не можете начать со стены." << endl;
 
    } while (lab[a][b] != '.');
 
    if (mazeTraverse(lab, a, b) == true)
        cout << endl << "Выход найден!" << endl;
 
    system("pause");
    return 0;
}
 
 
bool mazeTraverse(char lab[][13], int row, int column)
{
    static int turn = 0;
 
    if (turn >= 4 || turn <= -4)
        turn = turn % 4;
    if (turn < 0)
        turn = 4 + turn;
    if (row == 0 || row == 11 || column == 0 || column == 11)
        return true;
 
 
    switch (turn)
    {
        case 0:
            if (lab[row + 1][column] == '#' && lab[row][column + 1] == '.' || lab[row][column + 1] == 'x')
            {
                lab[row][column] = 'x';
                column++;
                if (lab[row + 1][column] == '.' || lab[row + 1][column] == 'x')
                    turn++;
            }
            else
                if (lab[row + 1][column + 1] == '#' && lab[row][column + 1] == '.' || lab[row][column + 1] == 'x')
                {
                    lab[row][column] = 'x';
                    column++;
                }
                else
                {
                    if (lab[row + 1][column + 1] == '#' && lab[row][column + 1] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
        case 1:
            if (lab[row][column - 1] == '#' && lab[row + 1][column] == '.' || lab[row + 1][column] == 'x')
            {
                lab[row][column] = 'x';
                row++;
                if (lab[row][column - 1] == '.' || lab[row][column - 1] == 'x')
                    turn++;
            }
            else
                if (lab[row + 1][column - 1] == '#' && lab[row + 1][column] == '.' || lab[row + 1][column] == 'x')
                {
                    lab[row][column] = 'x';
                    row++;
                    if (lab[row + 1][column - 1] == '.' || lab[row + 1][column - 1] == 'x')
                        turn++;
                }
                else
                {
                    if (lab[row + 1][column - 1] == '#' && lab[row + 1][column] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
        case 2:
            if (lab[row - 1][column] == '#' && lab[row][column - 1] == '.' || lab[row][column - 1] == 'x')
            {
                lab[row][column] = 'x';
                column--;
                if (lab[row - 1][column] == '.' || lab[row - 1][column] == 'x')
                    turn++;
            }
            else
                if (lab[row - 1][column - 1] == '#' && lab[row][column - 1] == '.' || lab[row][column - 1] == 'x')
                {
                    lab[row][column] = 'x';
                    column--;
                }
                else
                {
                    if (lab[row - 1][column - 1] == '#' && lab[row][column - 1] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
        case 3:
            if (lab[row][column + 1] == '#' && lab[row - 1][column] == '.' || lab[row - 1][column] == 'x')
            {
                lab[row][column] = 'x';
                row--;
                if (lab[row][column + 1] == '.' || lab[row][column + 1] == 'x')
                    turn++;
            }
            else
                if (lab[row - 1][column + 1] == '#' && lab[row - 1][column] == '.' || lab[row - 1][column] == 'x')
                {
                    lab[row][column] = 'x';
                    row--;
                }
                else
                {
                    if (lab[row - 1][column + 1] == '#' && lab[row - 1][column] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
    }
 
    if (row == 0 || row == 11 || column == 0 || column == 11)
        lab[row][column] = 'x';
    system("cls");
    for (int i = 0; i < 12; i++)
        cout << lab[i] << endl;
    Sleep(300);
    mazeTraverse(lab, row, column);
    //return false;
}
З.Ы. Код рабочий. Можно скомпилить в VS10 и посмотреть, как работает.
Миниатюры
Создать программу, отыскивающую проход по лабиринту  
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
26.06.2013, 14:33  [ТС]     Создать программу, отыскивающую проход по лабиринту #6
Цитата Сообщение от Мимино Посмотреть сообщение
Делала когда то что то подобное. Без стека, конечно, но может найдете что полезное.
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
#include "stdafx.h"
#include <iostream>
#include <windows.h>
using namespace std;
 
bool mazeTraverse(char [][13], int, int);
 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    const int size = 13;
    char lab[size - 1][size] = {"############",
                            "#...#......#",
                            "#.#.#.####.#",
                            "###.#....#.#",
                            "#....###.#..",
                            "####.#.#.#.#",
                            "#..#.#.#.#.#",
                            "##.#.#.#.#.#",
                            "#........#.#",
                            "######.###.#",
                            "#......#...#",
                            "############"};
    int a, b;
 
    for (int i = 0; i < size - 1; i++)
        cout << lab[i] << endl;
 
    do
    {
        cout << endl << "Введите стартовые координаты через пробел: ";
        cin >> a >> b;
 
        if (lab[a][b] != '#')
            break;
        else
            cout << "Вы не можете начать со стены." << endl;
 
    } while (lab[a][b] != '.');
 
    if (mazeTraverse(lab, a, b) == true)
        cout << endl << "Выход найден!" << endl;
 
    system("pause");
    return 0;
}
 
 
bool mazeTraverse(char lab[][13], int row, int column)
{
    static int turn = 0;
 
    if (turn >= 4 || turn <= -4)
        turn = turn % 4;
    if (turn < 0)
        turn = 4 + turn;
    if (row == 0 || row == 11 || column == 0 || column == 11)
        return true;
 
 
    switch (turn)
    {
        case 0:
            if (lab[row + 1][column] == '#' && lab[row][column + 1] == '.' || lab[row][column + 1] == 'x')
            {
                lab[row][column] = 'x';
                column++;
                if (lab[row + 1][column] == '.' || lab[row + 1][column] == 'x')
                    turn++;
            }
            else
                if (lab[row + 1][column + 1] == '#' && lab[row][column + 1] == '.' || lab[row][column + 1] == 'x')
                {
                    lab[row][column] = 'x';
                    column++;
                }
                else
                {
                    if (lab[row + 1][column + 1] == '#' && lab[row][column + 1] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
        case 1:
            if (lab[row][column - 1] == '#' && lab[row + 1][column] == '.' || lab[row + 1][column] == 'x')
            {
                lab[row][column] = 'x';
                row++;
                if (lab[row][column - 1] == '.' || lab[row][column - 1] == 'x')
                    turn++;
            }
            else
                if (lab[row + 1][column - 1] == '#' && lab[row + 1][column] == '.' || lab[row + 1][column] == 'x')
                {
                    lab[row][column] = 'x';
                    row++;
                    if (lab[row + 1][column - 1] == '.' || lab[row + 1][column - 1] == 'x')
                        turn++;
                }
                else
                {
                    if (lab[row + 1][column - 1] == '#' && lab[row + 1][column] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
        case 2:
            if (lab[row - 1][column] == '#' && lab[row][column - 1] == '.' || lab[row][column - 1] == 'x')
            {
                lab[row][column] = 'x';
                column--;
                if (lab[row - 1][column] == '.' || lab[row - 1][column] == 'x')
                    turn++;
            }
            else
                if (lab[row - 1][column - 1] == '#' && lab[row][column - 1] == '.' || lab[row][column - 1] == 'x')
                {
                    lab[row][column] = 'x';
                    column--;
                }
                else
                {
                    if (lab[row - 1][column - 1] == '#' && lab[row][column - 1] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
        case 3:
            if (lab[row][column + 1] == '#' && lab[row - 1][column] == '.' || lab[row - 1][column] == 'x')
            {
                lab[row][column] = 'x';
                row--;
                if (lab[row][column + 1] == '.' || lab[row][column + 1] == 'x')
                    turn++;
            }
            else
                if (lab[row - 1][column + 1] == '#' && lab[row - 1][column] == '.' || lab[row - 1][column] == 'x')
                {
                    lab[row][column] = 'x';
                    row--;
                }
                else
                {
                    if (lab[row - 1][column + 1] == '#' && lab[row - 1][column] == '#')
                    {
                        lab[row][column] = 'x';
                        turn--;
                    }
                    else
                    {
                        lab[row][column] = 'x';
                        turn++;
                    }
                }
            break;
    }
 
    if (row == 0 || row == 11 || column == 0 || column == 11)
        lab[row][column] = 'x';
    system("cls");
    for (int i = 0; i < 12; i++)
        cout << lab[i] << endl;
    Sleep(300);
    mazeTraverse(lab, row, column);
    //return false;
}
З.Ы. Код рабочий. Можно скомпилить в VS10 и посмотреть, как работает.
Очень интересный код, но таки стек нужен)
+Предчую кучу вопросов от преподавателя не по теме
А за кода спасибо большое)
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
26.06.2013, 16:29     Создать программу, отыскивающую проход по лабиринту #7
@ololoshka(, тебе скорее всего нужен обход графа в глубину или DFS, он рекурсивный и похож на стек
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
26.06.2013, 18:29  [ТС]     Создать программу, отыскивающую проход по лабиринту #8
Цитата Сообщение от el_gato_de_Ch Посмотреть сообщение
@ololoshka(, тебе скорее всего нужен обход графа в глубину или DFS, он рекурсивный и похож на стек
Такого нам на лекциях точно не объясняли, та и по стеку поверхностно прошли, конечно. Срок сдачи задания поджимает, разбираться в "обход графа в глубину или DFS" времени, к сожалению, нет.
ViktorKozlov
133 / 125 / 2
Регистрация: 13.12.2012
Сообщений: 293
26.06.2013, 18:35     Создать программу, отыскивающую проход по лабиринту #9
Цитата Сообщение от ololoshka( Посмотреть сообщение
Создать программу, отыскивающую проход по лабиринту.
Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице.
Программа находит проход через лабиринт, двигаясь от заданного входа. После отыскания прохода программа выводит найденный путь в виде координат квадратов. Для хранения пути использовать стек.
Ого, точно такое же задание на курсовой делал
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
26.06.2013, 18:45  [ТС]     Создать программу, отыскивающую проход по лабиринту #10
Цитата Сообщение от ViktorKozlov Посмотреть сообщение
Ого, точно такое же задание на курсовой делал
печаль в том, что это у меня обычная лаба, причем по номеру ее, она не должна быть трудной...

Может быть у вас есть исходник программы?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2013, 18:45     Создать программу, отыскивающую проход по лабиринту
Еще ссылки по теме:

C++ Создать программу,которая находит минимальное из 3х чисел. Для нахождения минимального числа создать функцию
C++ Проход по массиву
Проход по лабиринту C++
Зацикливается прохождение по лабиринту C++

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

Или воспользуйтесь поиском по форуму:
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
26.06.2013, 18:45     Создать программу, отыскивающую проход по лабиринту #11
@ololoshka(, единственное для чего я тут вижу применение стека - восстановление пути,

Суть обхода графа в глубину - изложена вот тут почитайте.
Yandex
Объявления
26.06.2013, 18:45     Создать программу, отыскивающую проход по лабиринту
Ответ Создать тему
Опции темы

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