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

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

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

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

18.05.2011, 16:56. Просмотров 3793. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2011, 16:56     Волновой алгоритм
Посмотрите здесь:

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

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

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

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

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

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

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

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

Волновой алгоритм для двумерной матрицы - C++
Подскажите пожалуйста как реализовать правильно(и желательно быстро) потому что, нужно будет считать для 4х объектов. Вот код который я...

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

Как написать волновой алгоритм для трехмерного лабиринта? - C++
Трехмерный лабиринт выглядит следующим образом На примере 3*3*3 Числа 0,1,2... секторы лабиринта -1 проходимые участки -2 стенки ...

Волновой или А* или Алгоритм ЛИ - C++
Как можно упростить и написать этот алгоритм, в книге вроде ясно понятно, что из точки А к точке Б идут волны, каждая первая порождает...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
22.05.2011, 22:30  [ТС]     Волновой алгоритм #2
ну помогите, пожалуйста...
vaselo
24.05.2011, 18:10  [ТС]
  #3

Не по теме:

help me!

stark91
1 / 1 / 0
Регистрация: 07.05.2010
Сообщений: 55
24.05.2011, 18:56     Волновой алгоритм #4
Сосвсем недавно делал лабу по волновому алгоритму. Может быть чем-нибуть поможет.
Там много лишнего, так что надо еще переделать.
Вложения
Тип файла: zip wave.zip (2.6 Кб, 282 просмотров)
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;
}
Yandex
Объявления
25.05.2011, 02:31     Волновой алгоритм
Ответ Создать тему
Опции темы

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