Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Ctrannik
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 2
#1

Зацикливается прохождение по лабиринту - C++

07.03.2013, 10:31. Просмотров 640. Ответов 4
Метки нет (Все метки)

Суть задачи: даны матрица NxM, даны 2 точки точка входа в лабиринт и выхода(пока отрубил,беру поиск с верхней точки), необходимо пройтись по лабиринту и найти путь до выхода, если выхода нет то соответствующее сообщение, необязательно находить кратчайший путь, вывести эту же матрицу но с обозначением пройденного пути от начала к концу(любым символом),так то его надо в файл(но пока ладно),в данной матрице одна развилка беру пока без стека для проверки матрицу...
Беру для проверки матрицу:
1,1,0,1,1,
0,0,0,0,1,
1,1,1,0,1,
1,1,1,0,1,
1,1,1,0,1

если pDown(); поднять выше то все работает, для этой матрицы

Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <stack>
 
using namespace std;
 
//пока почти все переменные глобальные - позже в нормальный вид...
 
 //вводим матрицу 5х5
    int const mkY=5; 
    int const mkX=5;
 
//чтобы пока -1 не ставить везде
    int kY=mkY-1;
    int kX=mkX-1;
 
    int mat[mkY][mkX]={
        1,1,0,1,1,
        0,0,0,0,1,
        1,1,1,0,1,
        1,1,1,0,1,
        1,1,1,0,1
 
    };
 
    int posX = 0,
        posY = 0;
 
//Переменные
    //пустота
    //стена
    //позиция старта
    //позиция выхода
 
//Функции
void pLeft(void)//влево
{   
    if(mat[posY][posX-1]==0)
    {
        mat[posY][posX]=1;
        posX--;
    };
};
 
void pRight(void)//вправо
{
    if( (mat[posY][posX+1]==0) && (posX+1!=kX) ) 
    {
        mat[posY][posX]=1;
        posX++;
    };
};
 
void pDown(void)//вниз
{
    if(mat[posY+1][posX]==0)
    {
        mat[posY][posX]=1;
        posY++;     
    };
};
 
void pBottom(void)//вверх
{
    if(mat[posY-1][posX]==0)
    {
        mat[posY][posX]=1;
        posY--;     
    };
};
 
int main(int argc, char* argv[])
{
 
 
    //Выводит массив на экран
    for(int i = 0; i <= kY; i++)
        for(int j = 0; j<= kX; j++)
        {
            cout << mat[i][j] << ' ' ;
            if (j == kX) cout << endl;
        };
 
    cout << "- - - - - - -" << endl;
 
    int ST[2] = {0,1}, // 1.2 _start
        EN[2] = {4,2}; // 5.3 _end
 
//  int posX = 0,
//      posY = 0;
 
    posY = ST[0]; //позиция старта Строки  X
    posX = ST[1]; //позиция старта Столбца Y
 
    cout << "coordinats START: "<< posY << " " << posX << endl;
    cout << "coordinats END: "<< EN[0] << " " << EN[1] << endl;
 
    int kontr(0);
 
    posX=0;
    posY=0;
/* !!! нахождение точки выхода по углам, в ином случаи "Выхода нет!"  */
    //ищем точку входа сверху, 
    for (int j=0;j >= kX ;j++ )
        if (mat[0][j]==0){ 
    cout << 'z'<< posX <<endl;
            posX=j;
    cout << 'j'<< j <<endl;
        };
 
    for(int i=0; i <= kX;i++)
        if (mat[0][i]==0)posX=i;
 
//тестовые переменные
    int tm[10][10];//вместо стека
    int tt = 0;
 
    //mat[posY][posX]=1;
    while (kontr!=1)
    {
        //для проверки while, т.к условие в нём не работает!
          //if ((posY >= EN[0])&&(posX >= EN[1] ))kontr=1;
 
        if ((posY >= kY)&&(posX >= 1 ))kontr=1;
    
        cout << "Y=" << posY << " X=" << posX << endl;
 
        if(mat[posY][posX]==0)//текущая позиция ? = 0
        {
 
 
            //если после движения везде 1 
            if( ((mat[posY+1][posX]==1)&&(mat[posY-1][posX]==1)&&(mat[posY][posX+1]==1)&&(mat[posY][posX-1]==1))&&(tt>=1) )
            {
                mat[posY][posX]=1;
                posY = tm[0][0];
                posX = tm[0][1];
                mat[posY][posX]=0;
                cout<< "C>> " << "Y=" << posY << "X=" << posX <<endl;
                //tt --;
                tt = 0;
                //проверка не пустой ли стек, если да то прохода нет
            };
            
                
 
            //если после движения Д 0 
            if((posY<=kY)&&
                (
                ((mat[posY  ][posX+1]==0)&&(mat[posY  ][posX-1]==0))||//справа слева 
                ((mat[posY+1][posX  ]==0)&&(mat[posY  ][posX+1]==0))||//сверху справа
                ((mat[posY+1][posX  ]==0)&&(mat[posY-1][posX  ]==0))||//сверху снизу
                ((mat[posY+1][posX  ]==0)&&(mat[posY  ][posX-1]==0))||//сверху слева
                ((mat[posY  ][posX+1]==0)&&(mat[posY-1][posX  ]==0))||//справа снизу
                ((mat[posY  ][posX-1]==0)&&(mat[posY-1][posX  ]==0))  //слева снизу
                )       
              )
            {
                //сохранить позиции x y
                
                tm[0][0] = posY;
                tm[0][1] = posX;
                cout << "S<<" << " Y=" << posY << "X=" << posX <<endl;
                tt = 1;
                //сохраняем позицию в стек
                //tt ++;
            };
            pDown();//вниз
            pLeft();//влево
            pRight();//вправо
 
        };
 
    };
 
    cout << endl << "test END";
 
    getchar();
    return 1;
}

http://www.cyberforum.ru/cpp-beginners/thread774915.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2013, 10:31
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Зацикливается прохождение по лабиринту (C++):

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

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

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

Нужно создать программу отыскивающею короткий путь по лабиринту в двумерном массиве
Нужно создать программу отыскивающею короткий путь по лабиринту. Лабиринт...

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

4
egor2116
571 / 375 / 215
Регистрация: 20.01.2013
Сообщений: 1,135
07.03.2013, 17:11 #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
    const int width=5;
    const int height=5;
    int arr[width][height]={
        {1,1,0,1,1},
        {0,0,0,0,1},
        {1,1,1,0,1},
        {1,1,1,0,1},
        {1,1,1,0,1}
    };
    //Идем
    int i,j;
    for(i=width-1;i>=0;i--){
        for(j=width;j>=0;j--){
            if(arr[i][j]==0) arr[i][j]=9; //Отмечаем пройденный путь
        }
        if(arr[1][0]==9) {  //Условие выхода т.к. коор-ты выхода известны
                      cout<<"Выход найден";
                   break;
                 
                 }
    }
    //Отображаем выход
    for(int i=0;i<width;i++){
        for(int j=0;j<height;j++){
            cout<<arr[i][j];
        }
        cout<<endl;
    }
Вывод

11011
99991
11191
11191
11191
0
StormSpirit
6 / 6 / 2
Регистрация: 13.02.2013
Сообщений: 32
07.03.2013, 17:19 #3
Кажется, поиск пути в лабиринте делается через рекурсию... волновой алгоритм там, все дела... или я ошибаюсь?
0
egor2116
571 / 375 / 215
Регистрация: 20.01.2013
Сообщений: 1,135
07.03.2013, 17:28 #4
Понятия не имею, я не изучал алгоритмы поиска, но думаю алгоритмов достаточно много.
делается через рекурсию
Если это целесообразно.
Циклы пока ни кто не отменял.
0
Ctrannik
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 2
07.03.2013, 17:44 #5
попробую
0
07.03.2013, 17:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2013, 17:44
Привет! Вот еще темы с решениями:

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

Прохождение лабиринта
Приведенная ниже сетка единиц и нулей - двумерный массив, представляющий...

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

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


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

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

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