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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.79
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
18.05.2011, 16:56     Волновой алгоритм #1
Доброго времени суток, дорогие форумчане.
Никак не додумаю волновой алгоритм, помогите, кто чем может:
файл - матрица целых чисел, где минимальное число - начало, а начало+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++ Волновой алгоритм (шахматы, конь)
C++ Волновой алгоритм
Волновой алгоритм поиска пути C++
Волновой алгоритм для двумерной матрицы C++
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 Кб, 273 просмотров)
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     Волновой алгоритм
Ответ Создать тему
Опции темы

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