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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
aveschekist
0 / 0 / 0
Регистрация: 07.12.2010
Сообщений: 13
#1

Обход лабиринта - C++

03.06.2011, 12:59. Просмотров 2427. Ответов 0
Метки нет (Все метки)

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

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

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

Напишите рекурсивную функцию 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2011, 12:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обход лабиринта (C++):

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

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

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

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

Прохождение лабиринта - C++
Нужно пройти от 1 до 16 самым коротким путем. И вывести на экран количество шагов.

Прохождение лабиринта - C++
Как написать программу для прохождения лабиринта? У меня не получается. Саму программу можно не писать, а только алгоритм дайте и советы....

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.06.2011, 12:59
Привет! Вот еще темы с ответами:

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

Проход лабиринта в C++ - C++
Ребята, помогите...вобщем, необходимо пройти по лабиринту и найти самый короткий маршрут...лабиринт я создал, а как пройти по нему ума не...

Генерация лабиринта - C++
Разработать приложение, генерирующее лабиринт размером m x n клеток. Дополнительные условия: а) Вход и выход – произвольные клетки...

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


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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