1 / 1 / 0
Регистрация: 29.11.2014
Сообщений: 50
1

Лабиринт - волновой алгоритм

18.03.2015, 16:51. Показов 3266. Ответов 3
Метки нет (Все метки)

Помогите пожалуйста. Я написал код, который мне выведет на экран кратчайший путь...
Но чего-то не хватает....
Может создать цикл с предисловием (Iteration< MaxIteration) Внутри него расположить два вложенных друг в друга цикла для построчного просмотра нашего массива. Внутри них определить условие, что если элемент рабочего массива равен количеству итераций, то просматриваются соседние элементы Pre(i+1,j), RAB(i-1,j), Pre(i,j+1), Pre(i,j-1) по следующему правилу(рассмотрим данное правило на примере RAB(i-1,j)): 1) Если Pre(i-1,j)==101 , то есть точка является проходимой то Pre(i-1,j)=Iteration+1 2)Если Pre(i-1,j)==100, то выходим из данного, так как мы дошли до начальной точки. Аналогично и с другими элемента то есть у вас должно получиться в общей сумме 8 условий. После того, как мы покидаем построчный просмотр массива мы должны увеличить количество итераций на 1
///
ВОТ КОД
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
//
//  main.cpp
//  lab
//
//  Created by Dima Shorokhov on 08.03.15.
//  Copyright (c) 2015 Dima Shorokhov. All rights reserved.
//
 
#include <iostream>
using namespace std;
 
 
int main(int argc, const char * argv[]) {
    
    
        
        /*задание лабиринта*/
        int  A = 10;
        int  B = 10;
        
        int Lab [A][B]= {
            //0 - конечное поле
            //102 - неплоходимое поле
            //101 - проходимое поле
            //100-начальная точка
            102,102,102,102,102,102,102,102,102,102,102,
            102,  0,101,101,101,101,102,102,101,102,102,
            102,101,101,101,101,101,101,101,101,101,102,
            102,102,101,101,101,101,101,101,101,100,102,
            102,101,101,101,101,102,102,101,101,101,102,
            102,102,101,101,102,101,102,101,101,102,102,
            102,101,101,101,102,101,102,101,101,102,102,
            102,102,102,101,102,101,102,101,101,102,102,
            102,101,101,101,101,101,101,101,101,102,102,
            102,102,102,102,102,102,102,102,102,102,102,
            
            
        };
        
        /*рабочий массив - копия лабиринта*/
        
        int Pre [A][B]= {
            //0 - конечное поле
            //102 - неплоходимое поле
            //101 - проходимое поле
            //100-начальная точка
            102,102,102,102,102,102,102,102,102,102,102,
            102,  0,101,101,101,101,102,102,101,102,102,
            102,101,101,101,101,101,101,101,101,101,102,
            102,102,101,101,101,101,101,101,101,100,102,
            102,101,101,101,101,102,102,101,101,101,102,
            102,102,101,101,102,101,102,101,101,102,102,
            102,101,101,101,102,101,102,101,101,102,102,
            102,102,102,101,102,101,102,101,101,102,102,
            102,101,101,101,101,101,101,101,101,102,102,
            102,102,102,102,102,102,102,102,102,102,102,
            
        };
        
        
        int Iteration=0; //количество итераций, то есть прохождений волны
        int MaxIteration=100; //максимальное количество итераций
        
        int x=1,y=1;//координаты клетки в рабочем массиве
        int x1=0,y1=0;//координаты клетки в лабиринте
        int min=102;
        
        /*движение волны*/
        
        while (1)
        {
            if (Pre[x+1][y]<min) {
                min=Pre[x+1][y];
                x1=x+1;
                y1=y;
            }
            if (Pre[x-1][y]<min) {
                min=Pre[x-1][y];
                x1=x-1;
                y1=y;
            }
            if (Pre[x][y+1]<min) {
                min=Pre[x][y+1];
                x1=x;
                y1=y+1;
            }
            if (Pre[x][y-1]<min) {
                min=Pre[x][y-1];
                x1=x;
                y1=y-1;
            }
            
            x=x1;
            y=y1;
            
            if (Pre[x][y]==0) {
                break;
            }
            Lab[x1][y1]=-1//для того, чтобы видеть кратчайший путь
        }
        
        for (int i=0,i<A;i++)
        {
            for(int j=0,j<B;j++)
            {
                switch (Lab[i][j]) {
                    case 102:
                    {cout<<setw(3)<<'#';
                        break;}
                    case 101:
                    {cout<<setw(3)<<'.';
                        break;}
                    case 100:
                    {cout<<setw(3)<<'S';
                        break;}
                    case 0:
                    {cout<<setw(3)<<'F';
                        break;}
                    case -1:
                    {cout<<setw(3)<<'>';
                        break;}
                        
                        
                    default:
                        break;
                }
            }
        }
    
    cout<<endl;
        
        return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.03.2015, 16:51
Ответы с готовыми решениями:

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Волновой алгоритм
Скажите почему программа зацикливается. #include&lt;bits/stdc++.h&gt; using namespace std; int a =...

Волновой алгоритм
Подскажите пожалуйста, на сколько сложно изготовить из матрицы 0000 0000 0000 напр.4345 3234...

Волновой алгоритм
Здравствуйте, очень прошу помочь с реализацией волнового алгоритма только лишь с помощью матрицы...

3
21 / 21 / 26
Регистрация: 17.03.2015
Сообщений: 119
18.03.2015, 16:59 2
А код то сам компилируется? А то в массиве лабиринта многовато элементов. Да и А с В должны быть константами...

И setw() не вижу описания
0
1 / 1 / 0
Регистрация: 29.11.2014
Сообщений: 50
18.03.2015, 17:15  [ТС] 3
да, лишнее убрал и константы ввел..
обьявил setw
ошибки вот тут находит.. подчеркивает А и В ... НЕ ПОЙМУ!
C++
1
2
3
4
5
6
7
8
9
10
11
 for (int i=0,i<A;i++)
        {
            for(int j=0,j<B;j++)
            {
                switch (Lab[i][j]) {
                    case 102:
                    {cout<<setw(3)<<'#';
                        break;}
                    case 101:
                    {cout<<setw(3)<<'.';
                        break;}
Добавлено через 5 минут
у меня не получается сделать это
"создать цикл с предисловием (Iteration< MaxIteration) Внутри него расположить два вложенных друг в друга цикла для построчного просмотра нашего массива. Внутри них определить условие, что если элемент рабочего массива равен количеству итераций, то просматриваются соседние элементы Pre(i+1,j), Pre(i-1,j), Pre(i,j+1), Pre(i,j-1) по следующему правилу(рассмотрим данное правило на примере Pre(i-1,j)): 1) Если Pre(i-1,j)==101 , то есть точка является проходимой то Pre(i-1,j)=Iteration+1 2)Если Pre(i-1,j)==100, то выходим из данного, так как мы дошли до начальной точки. Аналогично и с другими элемента то есть у вас должно получиться в общей сумме 8 условий."
0
653 / 574 / 164
Регистрация: 13.12.2012
Сообщений: 2,124
18.03.2015, 17:19 4
Цитата Сообщение от dimashorokhov Посмотреть сообщение
C++
1
for (int i=0,i<A;i++)
таки ; надо разделять а не ,

C++
1
for (int i=0;i<A;i++)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.03.2015, 17:19

Волновой алгоритм
Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 20*20, причем координаты начала...

Волновой алгоритм
Доброго времени суток, дорогие форумчане. Никак не додумаю волновой алгоритм, помогите, кто чем...

Волновой алгоритм
Нужно найти кратчайший путь в лабиринте размерностью 10х10 , и выводить ответ. Помогите

Волновой алгоритм поиска пути
Добрый день. Реализую всем известный алгоритм поиска кратчайшего пути. Но не могу понять одну...


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

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

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