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

@aveschekist · Регистрация: 07.12.2010

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

Стал делать задачу из книги Дейтлов про лабиринт, и наткнулся на некоторую проблему.

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

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

Напишите рекурсивную функцию 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

Правильный ли у меня подход в реализации рекурсивных функций?
Или же даннай задача делается значительно проще( для данной постановки задачи)?

@Ko4_ka · 23.02.2018, 22:30

Здравствуйте, с тем учётом что я изучил у Дейтлов до этой задачи я написал так:

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

Новые блоги и статьи Все статьи Все блоги /
Реалии 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 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.