Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/48: Рейтинг темы: голосов - 48, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 07.12.2010
Сообщений: 13
1

Обход лабиринта

03.06.2011, 12:59. Показов 8910. Ответов 1
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Стал делать задачу из книги Дейтлов про лабиринт, и наткнулся на некоторую проблему.

Текст упражнения:

"Существует простой алгоритм прохода через лабиринт, который гарантирует, что вы найдете выход (если он, конечно, существует). Если лабиринт не имеет выхода, то вы вернетесь в тому месту, из которого вышли. Касайтесь правой рукой стены (которая находится справа от вас) и начинайте движение вперед. Все время касайтесь рукой стены. Если лабиринт поворачивает направо, вы должны следовать за поворотом стены направо. И если вы не будете отпускать руку, то в конечном счете вы доберетесь до выхода из лабиринта.

Напишите рекурсивную функцию mazeTraverse прохода через лабиринт. Функция должна получать в качестве аргументов массив символов 12 на 12, представляющий лабиринт, и отправную точку. В процессе поиска выхода из лабиринта mazeTraverse помещает символ X в каждый пройденный квадрат пути. Функция должна перерисовывать лабиринт после каждого перемещения, чтобы пользователь мог наблюдать процесс решения задачи."

В лабиринте:
  • '#' - стенки лабиринта;
  • '.' - дорожка в лабиринте;
  • 'X' - пройденный квадрат;

Мой фрагмент кода:
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

#include <iostream>
#include <iomanip>
#include <Windows.h>
 
using namespace std;
 
const int size1 = 12;
 
 
void mazeTraverse( char [][ size1 ], const int *const, const int *const );
void drawnLabirint( const char [][ size1 ], const int *const );
int motionDetection( char [][ size1 ], const int *const, const int *const );
 
 
int main()
{
    //const int size = 12;
    char labirint[ size1 ][ size1 ] = {  
                                           { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
                       { '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#' },
                       { '.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#', },
                       { '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#', },
                       { '#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.', },
                       { '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', },
                       { '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#', },
                       { '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#', },
                       { '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#', },
                       { '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#', },
                       { '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#', },
                       { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }
                                         };
    int i = 2;
    int j = 0;
 
    cout << "Go, go, go!!!\n\n";
 
    mazeTraverse( labirint, &i, &j );
 
    return 0;
} // end function main
 
int motionDetection( char a[][ size1 ], const int *const i, const int *const j )
{
    int motion;
 
    if( *j + 1 < size1 && a[ *i + 1 ][ *j ] == '#' )
        motion = 0;         // forward
    else if( *j - 1 != 0 &&  a[ *i - 1 ][ *j ] == '#' )
        motion = 1;                       // back
    else if( *i - 1 != 0 && a[ *i ][ *j + 1 ] == '#' )
        motion = 2;               // up
    else 
        motion = 3;              // down
 
    return motion;
} // end function motionDetection
 
void mazeTraverse( char a[ ][ size1 ], const int *const row, const int *const column )
{
    static int motion = motionDetection( a, row, column ); // ищем праваой рукой стену, при входе в лабиринт
 
    int i = *row;
    int j = *column;
    
    if( a[ i ][ j ] == '.' )
        a[ i ][ j ] = 'X';
    else 
        a[ i ][ j ] = '.';
 
    drawnLabirint( a, &size1 );
 
    switch( motion )
    {
        case 0:
            if( j + 1 < size1 && a[ i + 1 ][ j ] == '#' && a[ i ][ j + 1 ] != '#' )
                j++;
            else if( a[ i + 1 ][ j ] != '#' )               
                {
                    motion = 3;
                    i++;
                } // end if..else
            else if( a[ i - 1 ][ j ] != '#' )
                {
                    motion = 2;
                    i--;
                } // end if..else               
            else
                motion = 1;
            break;
 
        case 1:
            if ( j - 1 > 0 && a[ i - 1 ][ j ] == '#' && a[ i ][ j - 1 ] != '#' )
                j--;
            else if( a[ i - 1 ][ j ] != '#' )           
            {
                motion = 2;
                i--;
            } // end if..else
            else if( a[ i + 1 ][ j ] != '#' )
            {
                motion = 3;
                i++;
            } // end if..else
            else
                motion = 0;
            
            break;
 
        case 2:
            if( i - 1 > 0 && a[ i ][ j + 1 ] == '#' && a[ i - 1 ][ j ] != '#' )
                i--;
            else if( a[ i ][ j + 1 ] != '#' )           
            {
                motion = 0;
                j++;
            } // end if..else
            else if( a[ i ][ j - 1 ] != '#' )
            {
                motion = 1;
                j--;
            } // end if..else   
            else
                motion = 3;
            break;
 
        case 3:
            if( i + 1 < size1 && a[ i ][ j - 1 ] == '#' && a[ i + 1 ][ j ] != '#' )
                i++;
            else if( a[ i ][ j - 1 ] != '#' )
            {
                motion = 1;
                j--;
            } // if..else           
            else if( a[ i ][ j + 1 ] != '#' )
            {
                motion = 0;
                j++;
            } // if..else
            else
                motion = 2;
            break;
 
        default:
            cout << "Unknown command!!!\n\n";
            break;
    } // end switch
 
    if( i > 0 && i < size1 - 1 && j > 0 && j < size1 - 1 )
        mazeTraverse( a, &i, &j );
    else
    {
        a[ i ][ j ] = 'X';
        drawnLabirint( a, &size1 );
    } // end if..else
 
} // end function mazeTraverse
 
 
void drawnLabirint( const char a[][ size1 ], const int *const n )
{
    cout << endl;
 
    for( int i = 0; i < *n; i++ )
    {
        for( int j = 0; j < *n; j++ )
            cout << setw( 3 ) << a[ i ][ j ];       
 
        cout << endl;
    } // end for
    Sleep( 1000 );
} // end function drawnLabirint
Правильный ли у меня подход в реализации рекурсивных функций?
Или же даннай задача делается значительно проще( для данной постановки задачи)?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 03.06.2011, 12:59
Ответы с готовыми решениями:

Обход лабиринта
Добрый вечер. Стоит задача обойти лабиринт, заданный матрицей (вводятся размерности и начальное...

Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход"
Ребятаа, обьясните чем различается: Обход в прямом направлении и Итерационный прямой обход ...

Выход из лабиринта
Всем привет, возник вопрос по поводу лабиринта. Посмотрев форум не нашел такого же задания. Суть -...

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

1
6 / 4 / 3
Регистрация: 07.12.2017
Сообщений: 18
23.02.2018, 22:30 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

//8.25 Дейтлы стр. 582 Обход лабиринта. #35 .46 x120
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>
using namespace std;
 
//глобальные переменные для того, что бы рекурсивная функция не ходила назад, то есть эти переменные
//хранят предыдущий ход
int X;
int Y;
 
int mazeTraverse(int[][12], int, int, int = 1); //аргумент по умолчанию используется для цикла
 
int main()
{
    //массив лабиринта
    int labyrinth[12][12] =
    {
        { 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35 },
        { 35, 46, 46, 46, 35, 46, 46, 46, 46, 46, 46, 35 },
        { 46, 46, 35, 46, 35, 46, 35, 35, 35, 35, 46, 35 },
        { 35, 35, 35, 46, 35, 46, 46, 46, 46, 35, 46, 35 },
        { 35, 46, 46, 46, 46, 35, 35, 35, 46, 35, 46, 46 },
        { 35, 35, 35, 35, 46, 35, 46, 35, 46, 35, 46, 35 },
        { 35, 46, 46, 35, 46, 35, 46, 35, 46, 35, 46, 35 },
        { 35, 35, 46, 35, 46, 35, 46, 35, 46, 35, 46, 35 },
        { 35, 46, 46, 46, 46, 46, 46, 46, 46, 35, 46, 35 },
        { 35, 35, 35, 35, 35, 35, 46, 35, 35, 35, 46, 35 },
        { 35, 46, 46, 46, 46, 46, 46, 35, 46, 46, 46, 35 },
        { 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35 },
    };
 
    //переменные для определения отправной точки
    int i;
    int j;
 
    //рандомно засеять отправную точку в массив
    srand(time(0));
    do
    {
        i = 1 + rand() % 11;
        j = 1 + rand() % 11;
    } while (labyrinth[i][j] == 35);
 
    Y = i;
    X = j;
 
    mazeTraverse(labyrinth, i, j);
    cout << "\nyou found a way out\n";
    return 0;
}
 
int mazeTraverse(int m[][12], int y, int x , int c)
{
    system("pause");
 
    //присваивание текущей позиции "x"
    m[y][x] = 120;
 
    //вывод массива
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 12; j++)
            cout << setw(2) << static_cast <char>(m[i][j]);
        cout << endl;
    }
 
    //проверка на выход из лабиринта
    if (y == 0 || x == 0 || y == 11 || x == 11)
    {
        return 0;
    }
    
    //присваивание текущей позиции "."
    m[y][x] = 46;
 
    //цикл на приоритет ходов
    while (c != 5)
    {
        //ход 1
        if (c == 1 && m[y - 1][x] == 46 && (y - 1) != Y) //если ок, ходим наверх
        {
            if (m[y - 1][x] == 46 && m[y][x + 1] == 46 && (x + 1) != X) //если ок, ходим направо
            {
                c = 2;
                Y = y;
                X = x;
                return mazeTraverse(m, y, x + 1, c);
            }
            c = 1;
            Y = y;
            X = x;
            return mazeTraverse(m, y - 1, x, c);
        }
        else if (c == 1 && m[y - 1][x] == 35 && m[y][x + 1] == 35 && m[y][x - 1] == 35) //если зашли в тупик, то ходим назад
            Y = 0;
        //ход 2
        if (c == 2 && m[y][x + 1] == 46 && (x + 1) != X) //если ок, ходим напрво
        {
            if (m[y][x + 1] == 46 && m[y + 1][x] == 46 && (y + 1) != Y) //если ок, ходим вниз
            {
                c = 3;
                Y = y;
                X = x;
                return mazeTraverse(m, y + 1, x, c);
            }
            c = 2;
            Y = y;
            X = x;
            return mazeTraverse(m, y, x + 1, c);
        }
        else if (c == 2 && m[y - 1][x] == 35 && m[y][x + 1] == 35 && m[y + 1][x] == 35) //если зашли в тупик, то ходим назад
            X = 0;
        //ход 3
        if (c == 3 && m[y + 1][x] == 46 && (y + 1) != Y) //если ок, ходим вниз
        {
            if (m[y + 1][x] == 46 && m[y][x - 1] == 46 && (x - 1) != X) //если ок, ходим налево
            {
                c = 4;
                Y = y;
                X = x;
                return mazeTraverse(m, y, x - 1, c);
            }
            c = 3;
            Y = y;
            X = x;
            return mazeTraverse(m, y + 1, x, c);
        }
        else if (c == 3 && m[y + 1][x] == 35 && m[y][x + 1] == 35 && m[y][x - 1] == 35) //если зашли в тупик, то ходим назад
            Y = 0;
        //ход 4
        if (c == 4 && m[y][x - 1] == 46 && (x - 1) != X) //если ок, ходим налево
        {
            if (m[y][x - 1] == 46 && m[y - 1][x] == 46 && (y - 1) != Y) //если ок, ходим наверх
            {
                c = 1;
                Y = y;
                X = x;
                return mazeTraverse(m, y - 1, x, c);
            }
            c = 4;
            Y = y;
            X = x;
            return mazeTraverse(m, y, x - 1, c);
        }
        else if (c == 4 && m[y - 1][x] == 35 && m[y + 1][x] == 35 && m[y][x - 1] == 35) //если зашли в тупик, то ходим назад
            X = 0;
        c++;
        if (c == 5)
            c = 1;
    }
}
0
23.02.2018, 22:30
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 23.02.2018, 22:30
Помогаю со студенческими работами здесь

Прохождение лабиринта
Как написать программу для прохождения лабиринта? У меня не получается. Саму программу можно не...

Прохождение лабиринта
Всем привет! Преподаватель по ОАиП дал задание. Учусь на специальность не связанную с...

Покраска лабиринта
Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть...

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


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru