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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
[O]Clic[K]
1 / 1 / 0
Регистрация: 28.03.2012
Сообщений: 55
#1

Волновой алгоритм - C++

06.09.2013, 21:36. Просмотров 2405. Ответов 15
Метки нет (Все метки)

Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 20*20, причем координаты начала и конца вводятся пользователем, исходный "лабиринт" считается заданным. Нужно вывести три матрицы. Первая исходная, вторая, заполненная итерациями, третья с конечным маршрутом... Помогите пожалуйста. Пока пытаюсь реализовать на матрице 7*7.
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
180
181
#include "stdafx.h"
#include <iostream>
#include <iomanip>
 
using namespace std;
 
const int M=7;
 
const int N=7;
 
int main()
{
// 0 – конечная точка
 
// 51 – непроходимая точка
 
// 50 – проходимая точка
 
// 49 –начальная точка
 
// инициализируем массив с игровым полем
 
int a_x, a_y, b_x, b_y;
 
int map[M][N]={
 
       51, 51, 51, 51, 51, 51, 51,
 
       51, 50, 50, 50, 50, 51, 51,
 
       51, 50, 50, 51, 50, 50, 51,
 
       51, 51, 50, 50, 50, 50, 51,
 
       51, 50, 50, 50, 51, 50, 51,
 
       51, 50, 51, 50, 50, 50, 51,
 
       51, 51, 51, 51, 51, 51, 51,
 
       };
 
cout<<"A:"<<endl;
cin>>a_x;
cin>>a_y;
cout<<"B:"<<endl;
cin>>b_x;
cin>>b_y;
 
map[a_x][a_y]=49;
map[b_x][b_y]=0;
 
for(int i=0;i<M;i++)
    {for(int j=0;j<N;j++)
        {
            switch(map[i][j]){
        case 51:
    {cout<<setw(3)<<'#';
    break;}
        case 50:
    {cout<<setw(3)<<'.';
    break;}
        case 49:
    {cout<<setw(3)<<'A';
    break;}
        case 0:
    {cout<<setw(3)<<'B';
    break;}
        }
    }
cout<<endl;
}
 
 
int tempmap[M][N]={
 
       51, 51, 51, 51, 51, 51, 51,
 
       51, 50, 50, 50, 50, 51, 51,
 
       51, 50, 50, 51, 50, 50, 51,
 
       51, 51, 50, 50, 50, 50, 51,
 
       51, 50, 50, 50, 51, 50, 51,
 
       51, 50, 51, 50, 50, 50, 51,
 
       51, 51, 51, 51, 51, 51, 51,
 
       };
 
int iter=0;
int iterk=49;
    while(iter<iterk)
        {   
        for(int i=0;i<M;i++)
            {for(int j=0;j<N;j++)
                {
            if(tempmap[i][j]==iter)
                    {
        if(tempmap[i+1][j]==50)tempmap[i+1][j]=iter+1;
        if(tempmap[i-1][j]==50)tempmap[i-1][j]=iter+1;
        if(tempmap[i][j+1]==50)tempmap[i][j+1]=iter+1;
        if(tempmap[i][j-1]==50)tempmap[i][j-1]=iter+1;
 
        if(tempmap[i+1][j]==51)break;
        if(tempmap[i-1][j]==51)break;
        if(tempmap[i][j+1]==51)break;
        if(tempmap[i][j-1]==51)break;
 
                }
            }
        }
iter++;
}
 
int X(1),Y(1),X1(0),Y1(0);
 
int min(51);
while(1){
    if(tempmap[X+1][Y]<min)
        {min=tempmap[X+1][Y];
            X1=X+1;
            Y1=Y;
}
 
    if(tempmap[X-1][Y]<min)
        {min=tempmap[X-1][Y];
            X1=X-1;
            Y1=Y;
}
 
if(tempmap[X][Y+1]<min)
        {min=tempmap[X][Y+1];
            X1=X;
            Y1=Y+1;
}
 
if(tempmap[X][Y-1]<min)
        {min=tempmap[X][Y-1];
            X1=X;
            Y1=Y-1;
}
 
X=X1;
Y=Y1;
 
if(tempmap[X1][Y1]==0)break;
 
map[X1][Y1]=-1;
 
}
 
for(int i=0;i<M;i++){
    for(int j=0;j<N;j++){
        switch(map[i][j]){
case 51:
{cout<<setw(3)<<'#';
break;}
 
case 50:
{cout<<setw(3)<<'.';
break;}
 
case 49:{cout<<setw(3)<<'A';
break;}
 
case 0:{cout<<setw(3)<<'B';
break;}
 
case -1:{cout<<setw(3)<<'>';
break;}
}
}
cout<<endl;
}
 
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.09.2013, 21:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Волновой алгоритм (C++):

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

Волновой алгоритм - C++
Подскажите пожалуйста, на сколько сложно изготовить из матрицы 0000 0000 0000 напр.4345 3234 2123 3234 Только при помощи обычных...

Волновой алгоритм - C++
Здравствуйте, очень прошу помочь с реализацией волнового алгоритма только лишь с помощью матрицы весов неориентированного графа. Объясните...

Волновой алгоритм - C++
Доброго времени суток, дорогие форумчане. Никак не додумаю волновой алгоритм, помогите, кто чем может: файл - матрица целых чисел, где...

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

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

15
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
07.09.2013, 00:27 #2
Чет не вижу я здесь внятного волнового алгоритма...где стек?

Добавлено через 12 минут
Вон, даже схема и код есть)
http://ru.wikipedia.org/wiki/%D0%90%...C_%D0%9B%D0%B8
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 00:34 #3
Цитата Сообщение от monolit Посмотреть сообщение
где стек
Очередь должна быть.
0
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
07.09.2013, 11:02 #4
Да не принципиально(сам стек использовал всегда), даже массивом при желании обойтись можно... Все ж это лучше, чем циклом по все матрице гонять кучу раз.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 16:40 #5
Цитата Сообщение от monolit Посмотреть сообщение
даже массивом
Можно очередь и массивом реализовать, и стеком. Но очередь - она и в Африке очередь.
0
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
07.09.2013, 16:47 #6
вроде не о реализации очереди вопрос, не?)
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 17:28 #7
Цитата Сообщение от monolit Посмотреть сообщение
вроде не о реализации очереди вопрос, не?)
Нет. Я поправил твое
Цитата Сообщение от monolit Посмотреть сообщение
где стек?
0
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
07.09.2013, 20:51 #8
Я ж говорю, не принципиально, в чем хранить вершины текущей волны. Используются за один шаг они все то...
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 21:37 #9
Цитата Сообщение от monolit Посмотреть сообщение
Я ж говорю, не принципиально, в чем хранить вершины текущей волны. Используются за один шаг они все то...
Использовать их очередью - не важно как ты реализуешь, нужно использовать очередь, а не стек!
0
[O]Clic[K]
1 / 1 / 0
Регистрация: 28.03.2012
Сообщений: 55
15.09.2013, 13:26  [ТС] #10
Пытаюсь адаптировать под себя код с Википедии, пока вот так:
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
#include <stdio.h> 
#include <conio.h> 
#include <iostream> 
#include <math.h> 
 
using namespace std; 
 
const int N=10;
 
int map[N][N]= 
{ 
0,1,0,0,0,0,0,0,0,0, 
0,1,0,0,0,0,0,0,0,0, 
0,0,0,1,0,0,0,0,0,0, 
1,1,0,1,0,0,0,0,0,0, 
0,0,0,1,0,0,0,0,0,0, 
0,0,0,1,0,0,0,0,0,0, 
0,0,0,1,1,1,1,1,0,0, 
0,0,0,0,0,0,0,0,0,0, 
0,0,0,0,0,0,0,0,0,0, 
0,0,0,0,0,0,0,0,0,0, 
}; 
int tempMAP[10][10]; 
 
int a_x, a_y, b_x, b_y, len;
int px[N * N], py[N * N]; 
 
bool lee(int a_x, a_y, b_x, b_y)   
{
  int dx[4] = {1, 0, -1, 0};   
  int dy[4] = {0, 1, 0, -1};   
  int d, x, y, k;
  bool stop;
 
 
  d = 0;
  map[a_y][a_x] = 100;            
  do {
    stop = true;               
    for ( y = 0; y < N; ++y )
      for ( x = 0; x < N; ++x )
        if ( map[y][x] == d )                        
        {
          for ( k = 0; k < 4; ++k )                    
            if ( map[y + dy[k]][x + dx[k]] == 0 )
            {
              stop = false;                           
              map[y + dy[k]][x + dx[k]] = d + 1;                      
            }
        }
    d++;
  } while ( !stop && map[b_y][b_x] == 0 );
 
  if (map[b_y][b_x] == 0) return false;  
 
  len = map[y][x];              
  x = b_x;
  y = b_y;
  d = len;
  while ( d > 0 )
  {
    px[d] = x;
    py[d] = y;                   
    d--;
    for (k = 0; k < 4; ++k)
      if (map[y + dy[k]][x + dx[k]] == d)
      {
        x = x + dx[k];
        y = y + dy[k];           
        break;
      }
  }
  px[0] = a_x;
  py[0] = a_y;                 
  return true;
}
 
int main() 
{ 
int a_x, a_y, b_x, b_y;
 
cout<<"A:"<<endl;
cin>>a_x;
cin>>a_y;
cout<<"B:"<<endl;
cin>>b_x;
cin>>b_y;
 
map[a_x][a_y]=100;
map[b_x][b_y]=111;
 
for (int i=0; i<N; i++){
    for (int j=0; j<N; j++){
        switch (map[i][j]){
            case 0:{
                cout<<".";
                break;
                   }
            case 1:{
                cout<<"*";
                break;
                   }
            case 100:{
                cout<<"A";
                break;
                    }
            case 111:{
                cout<<"B";
                break;
                     }
        }
    }
    cout<<endl;
}
 
lee(a_x, a_y, b_x, b_y);
 
return 0;
}
Не могу понять, почему ругается на "a_y" в строке 28 error C2061: syntax error : identifier 'a_y'
0
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
15.09.2013, 13:34 #11
C++
1
bool lee(int a_x, int a_y, int b_x, int b_y)
А стек принципиально не используешь?)
0
[O]Clic[K]
1 / 1 / 0
Регистрация: 28.03.2012
Сообщений: 55
15.09.2013, 13:41  [ТС] #12
monolit, мне бы с этим разобраться, плюс за лето все забыл, да и не особо и шарил в сишнике(
0
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
15.09.2013, 15:29 #13
с эти очень громоздко, о стеком намного короче и легче. Да и нечего там разбираться... на худой конец, массивом можно пользоваться. Запихнуть туда все точки текущей волны. Затем, используя этот массив, создать другой с точками следующей волны. Поменять массивы местами и т.д.
0
[O]Clic[K]
1 / 1 / 0
Регистрация: 28.03.2012
Сообщений: 55
15.09.2013, 16:48  [ТС] #14
Воспользовался массивом, пока все работает, но почему то не могу вывести переходный массив, т.е. массив с проставленными шагами
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
#include "stdafx.h"
#include <iostream>
#include <iomanip>
 
using namespace std;
 
const int M=7;
 
const int N=7;
 
int main()
{
 
int POLE[M][N]={
 
       51, 51, 51, 51, 51, 51, 51,
 
       51, 49, 50, 50, 50, 51, 51,
 
       51, 50, 50, 51, 50, 50, 51,
 
       51, 51, 50, 50, 50, 50,  51,
 
       51, 50, 50, 50, 51, 50, 51,
 
       51,  0, 51, 50, 50, 50, 51,
 
       51, 51, 51, 51, 51, 51, 51,
 
       };
 
for(int i=0;i<M;i++)
{for(int j=0;j<N;j++)
{
switch(POLE[i][j]){
case 51:
{cout<<setw(3)<<'#';
break;}
case 50:
{cout<<setw(3)<<'.';
break;}
case 49:{cout<<setw(3)<<'A';
break;}
case 0:{cout<<setw(3)<<'B';
break;}
}
}
cout<<endl;
}
 
cout<<endl;
 
int RAB[M][N];
 
int iter(0);
int iterk(49);
 
for(int i=0;i<M;i++)
{for(int j=0;j<N;j++)
{RAB[i][j]=POLE[i][j];}
}
 
while(iter<iterk)
{
for(int i=0;i<M;i++)
{for(int j=0;j<N;j++)
{
 
if(RAB[i][j]==iter)
{
    if(RAB[i+1][j]==50){
        RAB[i+1][j]=iter+1;
        cout<<setw(3)<<RAB[i+1][j];}
 
    if(RAB[i-1][j]==50){
        RAB[i-1][j]=iter+1;
        cout<<setw(3)<<RAB[i-1][j];}
 
    if(RAB[i][j+1]==50){
        RAB[i][j+1]=iter+1;
        cout<<setw(3)<<RAB[i][j+1];}
 
    if(RAB[i][j-1]==50){
        RAB[i][j-1]=iter+1;
        cout<<setw(3)<<RAB[i][j-1];}
 
    if(RAB[i+1][j]==49){
        break;
        cout<<setw(3)<<RAB[i+1][j];}
 
    if(RAB[i-1][j]==49){
        break;
        cout<<setw(3)<<RAB[i-1][j];}
 
    if(RAB[i][j+1]==49){
        break;
        cout<<setw(3)<<RAB[i][j+1];}
 
    if(RAB[i][j-1]==49){
        break;
        cout<<setw(3)<<RAB[i][j-1];}
    else cout<<setw(3)<<RAB[i][j];
cout<<endl;
}
}
}
 
iter++;
}
 
int X(1),Y(1),X1(0),Y1(0);
 
int min(51);
while(1){
if(RAB[X+1][Y]<min)
{min=RAB[X+1][Y];
X1=X+1;
Y1=Y;
}
 
if(RAB[X-1][Y]<min)
{min=RAB[X-1][Y];
X1=X-1;
Y1=Y;
}
 
if(RAB[X][Y+1]<min){min=RAB[X][Y+1];
X1=X;
Y1=Y+1;
}
 
if(RAB[X][Y-1]<min){min=RAB[X][Y-1];
X1=X;
Y1=Y-1;
}
 
X=X1;
Y=Y1;
 
if(RAB[X1][Y1]==0)break;
 
POLE[X1][Y1]=-1;
 
}
 
for(int i=0;i<M;i++)
{
for(int j=0;j<N;j++)
{
switch(POLE[i][j]){
case 51:
{cout<<setw(3)<<'#';
break;}
 
case 50:
{cout<<setw(3)<<'.';
break;}
 
case 49:{cout<<setw(3)<<'A';
break;}
 
case 0:{cout<<setw(3)<<'B';
break;}
 
case -1:{cout<<setw(3)<<'>';
break;}
}
}
cout<<endl;
}
 
 
    return 0;
}
0
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
16.09.2013, 14:28 #15
Не про то я говорил, друг мой, не про то.
Рассказываю:
Создаешь два массива с элементами типа pair<int, int> - массивы координат.
Стартовая точка известна. Проверяешь вначале все точки вокруг стартовой и заносишь их в первый массив. Это - твоя стартовая волна. А затем в цикле:
Для каждой точки первого массива(т.е. волны) проверяешь все соседние, которые еще не участвовали в обработке(можно отдельно матрицу завести логическую, где уже обработанные точки помечать), и эти соседне необработанные заносишь во второй массив - это будет следующая волна.
После всего этого второй массив делаешь первым, первый-вторым, и новый второй очищаешь. И так до тех пор, пока в следующую волну не попадется конечная точка.
Ну, затем нужно сделать обратную трассировку - ну эт должно быть ясно...

А насчет твоего кода: вот здесь потенциальная опасность выхода заграницы массива
Цитата Сообщение от [O]Clic[K] Посмотреть сообщение
for(int i=0;i<M;i++)
{for(int j=0;j<N;j++)
{
if(RAB[i][j]==iter)
{
* * if(RAB[i+1][j]==50){
* * * * RAB[i+1][j]=iter+1;
* * * * cout<<setw(3)<<RAB[i+1][j];}
if(RAB[i-1][j]==50){
* * * * RAB[i-1][j]=iter+1;
* * * * cout<<setw(3)<<RAB[i-1][j];}
Например, при i=0 i-1=-1...
0
16.09.2013, 14:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.09.2013, 14:28
Привет! Вот еще темы с ответами:

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

Волновой алгоритм (шахматы, конь) - C++
Всем привет! Пытался написать волновой алгоритм для нахождения кратчайшего пути коня на шахматной доски из A-&gt;B. Но что-то у меня...

Tiled Map и волновой алгоритм - C++
Делаю игру пакман. Нашла, что для привидений хорошо подходит волновой алгоритм. Нашла примеры реализации -все они завязаны на двумерных...

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


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

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

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