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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.79
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
#1

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

18.05.2011, 16:56. Просмотров 3881. Ответов 4
Метки нет (Все метки)

Доброго времени суток, дорогие форумчане.
Никак не додумаю волновой алгоритм, помогите, кто чем может:
файл - матрица целых чисел, где минимальное число - начало, а начало+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
#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
#include <Windows.h>
using namespace std;
    int** file(int &m);//Считывание карты   
    void show(int** map,int m);//вывод карты
    int** mapcpy(int** map,int m);//копирование исходной карты
    void findcoords(int &xs,int &ys,int &xe,int &ye,int m,int **map);// нахождение начала-конца
void main()
{
    int W=0; //номер волны
    const int Wmax=300; //max кол-во итераци
    int m=0,is,js,ie,je;//координаты начала-конца
    int **map;
    map=file(m);//получили карту
    show(map,m);
    findcoords(is,js,ie,je,m,map);//определили начало-конец
    const int n=m;
    int** mapping=mapcpy(map,n);//копируем исходную карту (для проложения пути нужно будет)
    //--------------------------------------------------------------------
    while (W!=Wmax)
    {
        for (int i=is; i<m; i++)
        {
            for (int j=js; j<m; j++)
                 if(map[i][j]==W && i<m-1 && j<m-1)
                    {
                     if (map[i][j+1]!=-1||map[i][j+1]!=0)
                        map[i][j+1]=map[i][j+1]+W;
                     if (map[i+1][j]!=-1||map[i+1][j]!=0)
                        map[i+1][j]=map[i+1][j]+W;
                     if (map[i+1][j]!=-1||map[i+1][j]!=0 && i!=0 && j!=0)
                     }
        }
        W++;
    }
    //-------------------------------------------------------------------
cout<<"\nЛабиринт после алгоритма:"<<"\n \n";
show(map,m);
}
int** file(int &m)
{
    int **map;
    FILE* f;
    int i,j;
    char fname [80];
    cout<<"\nИмя (путь) к файлу: ";
    gets(fname);
    f=fopen(fname,"rt");
    if(f)
    {
        while(!feof(f))
        {
            if(fgetc(f)=='\n')
                m++;//Подсчет размера карты
        }
        fseek(f,0,SEEK_SET);
        map=new int* [m];
        for(i=0;i<m;i++)
            map[i]=new int [m];
        for(i=0;i<m;i++)
        {
            for(j=0;j<m;j++)
                fscanf(f,"%d",&map[i][j]);
        }
        fclose(f);
        return map;
    }
}
void findcoords(int &is,int &js,int &ie,int &je,int m,int **map)
{
    int s=map[0][0],e;
    is=js=ie=je=0;
      for (int i=0; i<m; i++)
        {for (int j=0; j<m; j++)
            {
            if (map[i][j]<s)//начало = минимальное число
                {
                    s=map[i][j]; 
                    is=i;
                    js=j;
                }
             }
      }
       for (int k=0; k<m; k++)
        {for (int l=0; l<m; l++)
            {
            if (map[k][l]==s+1)//конец=начало+1
                {
                    e=map[k][l];
                    ie=k;
                    je=l;
                    return;
                }
                
             }
      }
}
void show(int** map,int m)
{
for(int i=0; i<m; i++)
     {for(int j=0; j<m; j++)
        cout<<map[i][j]<<"\t"; 
    cout<<endl<<endl<<endl;
     }
 system ("pause");
 return;
}
int** mapcpy(int** map,int n)
{
    int** mapping;
    mapping=new int* [n];
    for(int i=0; i<n; i++)
    {
        mapping[i]=new int [n];
        for(int j=0; j<n; j++)
            mapping[i][j]=map[i][j];
     }
return mapping;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2011, 16:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Волновой алгоритм (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++
Нужно найти кратчайший путь в лабиринте размерностью 10х10 , и выводить ответ. Помогите

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

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

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

4
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
22.05.2011, 22:30  [ТС] #2
ну помогите, пожалуйста...
0
vaselo
24.05.2011, 18:10  [ТС]
  #3

Не по теме:

help me!

0
stark91
1 / 1 / 0
Регистрация: 07.05.2010
Сообщений: 55
24.05.2011, 18:56 #4
Сосвсем недавно делал лабу по волновому алгоритму. Может быть чем-нибуть поможет.
Там много лишнего, так что надо еще переделать.
1
Вложения
Тип файла: zip wave.zip (2.6 Кб, 284 просмотров)
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
25.05.2011, 02:31  [ТС] #5

Не по теме:

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



Добавлено через 3 часа 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
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
#include <stdlib.h>
#include <iostream>
#include <Windows.h>
using namespace std;
    int** file(int &m);//Считывание карты   
    void show(int** map,int m);//вывод карты
    int** mapcpy(int** map,int m);//копирование исходной карты
    int findcoords(int &xs,int &ys,int &xe,int &ye,int m,int **map);// нахождение начала-конца
void main()
{
    int W=0; //номер волны
    const int Wmax=300; //max кол-во итераци
    int m=0,is,js,ie,je;//координаты начала-конца
    int **map,s;
    map=file(m);//получили карту
    show(map,m);
    s=findcoords(is,js,ie,je,m,map);//определили начало-конец
    const int n=m;
    int** mapping=mapcpy(map,n);//копируем исходную карту (для проложения пути нужно будет)
    //--------------------------------------------------------------------
    int i,j,flag=0;
    while (flag!=1)
    {
        for (i=is; i<m; i++)
        {
            for (j=js; j<m; j++)
                { if(i<m-1 && j<m-1)
                    {
                    if (map[i][j-1]!=s+1 && j>0)
                        {
                            if(  map[i][j-1]+W>mapping[i][j-1]+W)
                                 map[i][j-1]=  mapping[i][j-1]+W;
                            else map[i][j-1]=      map[i][j-1]+W;
                    }
                    else {if(map[i][j-1]==s+1) flag=1;}
                    if(map[i-1][j]!=s+1 && i>0)
                        {
                            if(  map[i-1][j]+W>mapping[i-1][j]+W)
                                 map[i-1][j]=  mapping[i-1][j]+W;
                            else map[i-1][j]=      map[i-1][j]+W;
                         }
                    else {if(map[i-1][j]==s+1) flag=1;}
                    if(map[i+1][j]!=s+1 && i!=m-1)
                        {
                            if(  map[i+1][j]+W>mapping[i+1][j]+W)
                                 map[i+1][j]=  mapping[i+1][j]+W;
                            else map[i+1][j]=      map[i+1][j]+W;
                         }
                    else {if(map[i+1][j]==s+1) flag=1;}
                    if (map[i][j+1]!=s+1 && j>m-1)
                        {
                            if(  map[i][j+1]+W>mapping[i][j+1]+W)
                                 map[i][j+1]=  mapping[i][j+1]+W;
                            else map[i][j+1]=      map[i][j+1]+W;
                         }
                    else {if(map[i][j+1]==s+1) flag=1;}
                    }
                 W++;
            }
        }
    }
    //-------------------------------------------------------------------
cout<<"\nЛабиринт после алгоритма:"<<"\n \n";
show(map,m);
}
int** file(int &m)
{
    int **map;
    FILE* f;
    int i,j;
    char fname [80];
    cout<<"\nИмя (путь) к файлу: ";
    gets(fname);
    f=fopen(fname,"rt");
    if(f)
    {
        while(!feof(f))
        {
            if(fgetc(f)=='\n')
                m++;//Подсчет размера карты
        }
        fseek(f,0,SEEK_SET);
        map=new int* [m];
        for(i=0;i<m;i++)
            map[i]=new int [m];
        for(i=0;i<m;i++)
        {
            for(j=0;j<m;j++)
                fscanf(f,"%d",&map[i][j]);
        }
        fclose(f);
        return map;
    }
}
int findcoords(int &is,int &js,int &ie,int &je,int m,int **map)
{
    int s=map[0][0],e;
    is=js=ie=je=0;
      for (int i=0; i<m; i++)
        {for (int j=0; j<m; j++)
            {
            if (map[i][j]<s)//начало = минимальное число
                {
                    s=map[i][j]; 
                    is=i;
                    js=j;
                }
             }
      }
       for (int k=0; k<m; k++)
        {for (int l=0; l<m; l++)
            {
            if (map[k][l]==s+1)//конец=начало+1
                {
                    e=map[k][l];
                    ie=k;
                    je=l;
                    return s;
                }
                
             }
      }
       return s;
}
void show(int** map,int m)
{
for(int i=0; i<m; i++)
     {for(int j=0; j<m; j++)
        cout<<map[i][j]<<"\t"; 
    cout<<endl<<endl<<endl;
     }
 system ("pause");
 return;
}
int** mapcpy(int** map,int n)
{
    int** mapping;
    mapping=new int* [n];
    for(int i=0; i<n; i++)
    {
        mapping[i]=new int [n];
        for(int j=0; j<n; j++)
            mapping[i][j]=map[i][j];
     }
return mapping;
}
0
25.05.2011, 02:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2011, 02:31
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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