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

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

Войти
Регистрация
Восстановить пароль
 
Ctrannik
0 / 0 / 0
Регистрация: 03.03.2013
Сообщений: 2
#1

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

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

Проход по лабиринту - C++
Описать класс, реализующий стек. Написать программу, использующую этот класс для отыскания прохода по лабиринту. Лабиринт...

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

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

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

Нужно создать программу отыскивающею короткий путь по лабиринту в двумерном массиве - C++
Нужно создать программу отыскивающею короткий путь по лабиринту. Лабиринт представлен в виде квадрата(двумерного массива) из 0 и 1. Ход по...

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

4
egor2116
342 / 373 / 42
Регистрация: 20.01.2013
Сообщений: 1,132
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
342 / 373 / 42
Регистрация: 20.01.2013
Сообщений: 1,132
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
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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