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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
[O]Clic[K]
1 / 1 / 0
Регистрация: 28.03.2012
Сообщений: 55
06.09.2013, 21:36     Волновой алгоритм #1
Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.09.2013, 21:36     Волновой алгоритм
Посмотрите здесь:

C++ Волновой алгоритм
C++ Волновой алгоритм (шахматы, конь)
C++ Волновой алгоритм
Волновой алгоритм поиска пути C++
Волновой алгоритм для двумерной матрицы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
07.09.2013, 00:27     Волновой алгоритм #2
Чет не вижу я здесь внятного волнового алгоритма...где стек?

Добавлено через 12 минут
Вон, даже схема и код есть)
http://ru.wikipedia.org/wiki/%D0%90%...C_%D0%9B%D0%B8
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 00:34     Волновой алгоритм #3
Цитата Сообщение от monolit Посмотреть сообщение
где стек
Очередь должна быть.
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
07.09.2013, 11:02     Волновой алгоритм #4
Да не принципиально(сам стек использовал всегда), даже массивом при желании обойтись можно... Все ж это лучше, чем циклом по все матрице гонять кучу раз.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 16:40     Волновой алгоритм #5
Цитата Сообщение от monolit Посмотреть сообщение
даже массивом
Можно очередь и массивом реализовать, и стеком. Но очередь - она и в Африке очередь.
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
07.09.2013, 16:47     Волновой алгоритм #6
вроде не о реализации очереди вопрос, не?)
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 17:28     Волновой алгоритм #7
Цитата Сообщение от monolit Посмотреть сообщение
вроде не о реализации очереди вопрос, не?)
Нет. Я поправил твое
Цитата Сообщение от monolit Посмотреть сообщение
где стек?
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
07.09.2013, 20:51     Волновой алгоритм #8
Я ж говорю, не принципиально, в чем хранить вершины текущей волны. Используются за один шаг они все то...
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.09.2013, 21:37     Волновой алгоритм #9
Цитата Сообщение от monolit Посмотреть сообщение
Я ж говорю, не принципиально, в чем хранить вершины текущей волны. Используются за один шаг они все то...
Использовать их очередью - не важно как ты реализуешь, нужно использовать очередь, а не стек!
[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'
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
15.09.2013, 13:34     Волновой алгоритм #11
C++
1
bool lee(int a_x, int a_y, int b_x, int b_y)
А стек принципиально не используешь?)
[O]Clic[K]
1 / 1 / 0
Регистрация: 28.03.2012
Сообщений: 55
15.09.2013, 13:41  [ТС]     Волновой алгоритм #12
monolit, мне бы с этим разобраться, плюс за лето все забыл, да и не особо и шарил в сишнике(
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
15.09.2013, 15:29     Волновой алгоритм #13
с эти очень громоздко, о стеком намного короче и легче. Да и нечего там разбираться... на худой конец, массивом можно пользоваться. Запихнуть туда все точки текущей волны. Затем, используя этот массив, создать другой с точками следующей волны. Поменять массивы местами и т.д.
[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;
}
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 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...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.09.2013, 14:59     Волновой алгоритм
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
[O]Clic[K]
1 / 1 / 0
Регистрация: 28.03.2012
Сообщений: 55
19.09.2013, 14:59  [ТС]     Волновой алгоритм #16
Методом проб и ошибок получилось что-то такое, можно как-то все это упростить?!)
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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include "stdafx.h"
#include <iostream>
#include <iomanip>
 
using namespace std;
 
const int M=22;
 
/*
111- непроходимая
110-проходимая
100-конечная
0-начальная
 
*/
void print_map(int mas[M][M])
{
    cout<<endl;
    for(int i=1;i<M-1;i++)
    {
        for(int j=1;j<M-1;j++)
        {
            switch(mas[i][j])
            {
            case 111:
                {
                cout<<setw(3)<<"#";
                break;
                }
            case 110:
                {
                cout<<setw(3)<<".";
                break;
                }
            case 100:
                {
                cout<<setw(3)<<"A";
                break;
                }
            case 0:
                {
                cout<<setw(3)<<"B";
                break;
                }
            case -1:
                {
                cout<<setw(3)<<">";
                break;
                }
 
 
 
            }
 
        }
        cout<<endl;
    }
}
 
int main()
{
    int MAP[M][M]={
    
        111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,
        111,110,111,111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,111,110,111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,111,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,111,111,111,111,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,111,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,111,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,111,111,
        111,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,111,110,111,
        111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,111,
};
    int X3,Y3,X4,Y4;
    setlocale(LC_CTYPE,"rus");
    cout<<"Введите X точки A:";
    cin>>X3;
    cout<<"Введите Y точки A:";
    cin>>Y3;
    MAP[X3+1][Y3+1]=100;
 
    cout<<"Введите X точки B:";
    cin>>X4;
    cout<<"Введите Y точки B:";
    cin>>Y4;
    MAP[X4+1][Y4+1]=0;
 
    print_map(MAP);
    int RAB[M][M];
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)RAB[i][j]=MAP[i][j];
 
 
 
int iter(0), iterk(100);
while(iter<iterk)
{
for(int i=0;i<M;i++) 
{
for(int j=0;j<M;j++)
{
 
if(RAB[i][j]==iter)
{
 
if(RAB[i+1][j]==110)RAB[i+1][j]=iter+1;
if(RAB[i-1][j]==110)RAB[i-1][j]=iter+1;
if(RAB[i][j+1]==110)RAB[i][j+1]=iter+1;
if(RAB[i][j-1]==110)RAB[i][j-1]=iter+1;
 
if(RAB[i+1][j]==0)break;
if(RAB[i-1][j]==0)break;
if(RAB[i][j+1]==0)break;
if(RAB[i][j-1]==0)break;
 
}
}
}
iter++;
}
 
if((RAB[X4+1+1][Y4+1]==111 || RAB[X4+1+1][Y4+1]==110) && (RAB[X4-1+1][Y4+1]==110 || RAB[X4-1+1][Y4+1]==111) && (RAB[X4+1][Y4]==110 ||RAB[X4+1][Y4]==111) && (RAB[X4+1][Y4+2]==111 ||RAB[X4+1][Y4+2]==110) )return 0;
if((RAB[X3+1+1][Y3+1]==111 || RAB[X3+1+1][Y3+1]==110) && (RAB[X3-1+1][Y3+1]==110 || RAB[X3-1+1][Y3+1]==111) && (RAB[X3+1][Y3]==110 ||RAB[X3+1][Y3]==111) && (RAB[X3+1][Y3+2]==111 ||RAB[X3+1][Y3+2]==110) )return 0;
 
cout<<endl;
for(int i=1;i<M-1;i++)
{
    for(int j=1;j<M-1;j++)
    {
 
        cout<<setw(3)<<RAB[i][j];
        
    }
    cout<<endl;
}
int X=X3+1,Y=Y3+1,X1(0),Y1(0);
 
int min(111);
 
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;
 
MAP[X1][Y1]=-1;
 
}
 
print_map(MAP);
    return 0;
}
Yandex
Объявления
19.09.2013, 14:59     Волновой алгоритм
Ответ Создать тему
Опции темы

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