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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
#1

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

26.06.2013, 12:35. Просмотров 1505. Ответов 10
Метки нет (Все метки)

Создать программу, отыскивающую проход по лабиринту.
Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице.
Программа находит проход через лабиринт, двигаясь от заданного входа. После отыскания прохода программа выводит найденный путь в виде координат квадратов. Для хранения пути использовать стек.

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

0 1 1
0 0 0
1 1 0

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

Знаю заезженная тема, есть куча постов об этом на форуме, в других сайтах и методичках, но ничего толкового я, к сожалению, не нашел. Помогите, пожалуйста, с реализацией...
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.06.2013, 12:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Создать программу, отыскивающую проход по лабиринту (C++):

Программу, отыскивающую проход по лабиринту - C++
Написать программу, отыскивающую проход по лабиринту, с ис-пользованием контейнерного класса stack из STL. Лабиринт пред-ставляется в виде...

Проход по лабиринту - C++
Описать класс, реализующий стек. Написать программу, использующую этот класс для отыскания прохода по лабиринту. Лабиринт...

Проход по лабиринту - C++
Привет всем. Помогите пожалуйста с задачей на С/C++ идёт практика я не понимаю как сделать задачу просто даже не представляю училка...

Нужно создать программу отыскивающею короткий путь по лабиринту в двумерном массиве - C++
Нужно создать программу отыскивающею короткий путь по лабиринту. Лабиринт представлен в виде квадрата(двумерного массива) из 0 и 1. Ход по...

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

Создать программу, отыскивающую проход по лабиринту - C (СИ)
Создать программу на СИ, отыскивающую проход по лабиринту. Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат...

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

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

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

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

Какие у вас мысли по поводу вашей задачи?
граф невзвешанный тут и DFS с BFS'ом подойдут.
1
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;
}
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 и посмотреть, как работает.
2
Миниатюры
Создать программу, отыскивающую проход по лабиринту  
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 и посмотреть, как работает.
Очень интересный код, но таки стек нужен)
+Предчую кучу вопросов от преподавателя не по теме
А за кода спасибо большое)
0
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
26.06.2013, 16:29 #7
@ololoshka(, тебе скорее всего нужен обход графа в глубину или DFS, он рекурсивный и похож на стек
1
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
26.06.2013, 18:29  [ТС] #8
Цитата Сообщение от el_gato_de_Ch Посмотреть сообщение
@ololoshka(, тебе скорее всего нужен обход графа в глубину или DFS, он рекурсивный и похож на стек
Такого нам на лекциях точно не объясняли, та и по стеку поверхностно прошли, конечно. Срок сдачи задания поджимает, разбираться в "обход графа в глубину или DFS" времени, к сожалению, нет.
0
ViktorKozlov
133 / 125 / 2
Регистрация: 13.12.2012
Сообщений: 293
26.06.2013, 18:35 #9
Цитата Сообщение от ololoshka( Посмотреть сообщение
Создать программу, отыскивающую проход по лабиринту.
Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице.
Программа находит проход через лабиринт, двигаясь от заданного входа. После отыскания прохода программа выводит найденный путь в виде координат квадратов. Для хранения пути использовать стек.
Ого, точно такое же задание на курсовой делал
1
ololoshka(
1 / 1 / 0
Регистрация: 17.12.2011
Сообщений: 13
26.06.2013, 18:45  [ТС] #10
Цитата Сообщение от ViktorKozlov Посмотреть сообщение
Ого, точно такое же задание на курсовой делал
печаль в том, что это у меня обычная лаба, причем по номеру ее, она не должна быть трудной...

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

Суть обхода графа в глубину - изложена вот тут почитайте.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2013, 18:45
Привет! Вот еще темы с ответами:

Создание программы, отыскивающей проход по лабиринту - PascalABC.NET
Создать программу, отыскивающую проход по лабиринту. Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо...

Составьте программу отыскивающую наибольший элемент одномерного массива - QBasic
Составьте программу отыскивающую наибольший элемент одномерного массива A(n) из числа принадлежаших интервалу (min,(min+max/2)). (min и max...

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

Составить программу, отыскивающую в одномерном массиве пары элементов - PascalABC.NET
Составьте программу, отыскивающую среди пар элементов одномерного массива Z (N) те, разность между элементами которых есть величина...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.06.2013, 18:45
Ответ Создать тему
Опции темы

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