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

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

Восстановить пароль Регистрация
 
Ctrannik
Сообщений: n/a
07.03.2013, 10:31     Зацикливается прохождение по лабиринту #1
Суть задачи: даны матрица 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2013, 10:31     Зацикливается прохождение по лабиринту
Посмотрите здесь:

C++ проход по лабиринту
Программу, отыскивающую проход по лабиринту C++
C++ Прохождение лабиринта
C++ Прохождение лабиринта
Проход по лабиринту C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
egor2116
 Аватар для egor2116
337 / 368 / 42
Регистрация: 20.01.2013
Сообщений: 1,100
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
StormSpirit
 Аватар для StormSpirit
6 / 6 / 2
Регистрация: 13.02.2013
Сообщений: 32
07.03.2013, 17:19     Зацикливается прохождение по лабиринту #3
Кажется, поиск пути в лабиринте делается через рекурсию... волновой алгоритм там, все дела... или я ошибаюсь?
egor2116
 Аватар для egor2116
337 / 368 / 42
Регистрация: 20.01.2013
Сообщений: 1,100
07.03.2013, 17:28     Зацикливается прохождение по лабиринту #4
Понятия не имею, я не изучал алгоритмы поиска, но думаю алгоритмов достаточно много.
делается через рекурсию
Если это целесообразно.
Циклы пока ни кто не отменял.
Ctrannik
Сообщений: n/a
07.03.2013, 17:44     Зацикливается прохождение по лабиринту #5
попробую
Yandex
Объявления
07.03.2013, 17:44     Зацикливается прохождение по лабиринту
Ответ Создать тему
Опции темы

Текущее время: 00:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru