Минимальный путь между двух точек

@paskalnikita · Регистрация: 12.08.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте! Я бы хотел сделать простенькую программу, которая бы находила минимальный путь между двух точек. Сделал я пока что-то такое :

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
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
 
int main()
{
    srand(time(NULL));
    int side;
    cout<<"Tell a size of the side of square:";
    cin>>side;
    if(side>0)
    {
        char **square = new char*[side];
        for (int i = 0; i < side; i++)
        {
            square[i] = new char[side];
        }
        int x1,y1,x2,y2,answer;
 
        cout<<"Do you want to enter coordinates?(1-yes;0-no)";
        cin>>answer;
        if(answer==1)
        {
            cout<<"Enter x1=";
            cin>>x1;
            cout<<"Enter y1=";
            cin>>y1;
            cout<<"Enter x2=";
            cin>>x2;
            cout<<"Enter y2=";
            cin>>y2;
            if(x1>side || y1>side || x2>side || y2 > side)
            {
                cout<<"You entered wrong values of coordinates";
                return 0;
            }
        }
        else
        {
            x1=rand()%side+1;
            y1=rand()%side+1;
 
            x2=rand()%side+1;
            y2=rand()%side+1;
        }
 
        for(int j=side; j>0; j--)
        {
            for(int i=1; i<=side; i++)
            {
                if((i-1)==x1-1 && (j-1)==y1-1)
                {
                    square[i-1][j-1]='+';
                }
                else if((i-1)==x2-1 && (j-1)==y2-1)
                {
                    square[i-1][j-1]='+';
                }
                else
                {
                    square[i-1][j-1]='*';
                }
                //cout<<"("<<i<<";"<<j<<")";
            }
            //cout<<endl;
        }
 
        cout<<"First point has coordinates ("<<x1<<";"<<y1<<")"<<endl;
        cout<<"Second point has coordinates ("<<x2<<";"<<y2<<")"<<endl;
        for(int j=side; j>0; j--)
        {
            for(int i=1; i<=side; i++)
            {
                cout<<square[i-1][j-1]<<" ";
            }
            cout<<endl;
        }
        float dist;
        double x,y;
        if(y1<y2)
        {
            y=y2-y1;
            if(x1<x2)
            {
                x=x2-x1;
            }
            else
            {
                x=x1-x2;
            }
        }
        else
        {
            y=y1-y2;
            if(x1<x2)
            {
                x=x2-x1;
            }
            else
            {
                x=x1-x2;
            }
        }
        dist = sqrt(x*x+y*y);
        cout<<"Distance between this two points is "<<dist;
        delete [] square;
    }
    else
    {
        cout<<"Side must be > 0";
    }
    return 0;
}

Тут я сделал двумерный массив, но он в виде координатной плоскости. То есть индексы элементов изменены так, чтобы соответствовать координатам как в обычной плоскости. Так вот, может есть где-то некие наброски для того,что я хочу(все то что я искал мне достаточно проблематично понять)? Сам я учу С++ только второй семестр и пока я застрял на этапе указателей и адресов(поэтому какие-то варианты с готовыми решениями мне не подходят). И хочу я сделать что-то типа такого : точки (1;1) (2;4) - минимальное кол-во шагов 4(если нельзя двигаться по диагонали) и 3(если разрешено). И суть проблемы в том, что по сути я хочу сделать так, чтобы была некая точка которая движется от одного пункта к другому.Вот только как стоит перебирать все направления(я имею ввиду ситуацию когда до точки можно двигаться верх и вправо или вправо и вверх - точки (1;1) (2;2)). Надеюсь, суть ясна. Заранее спасибо!

@mokojumbot · 22.05.2017, 03:26

в смысле "как"? зная координаты, по моему, очевидно, в какую сторону двигаться от каждой точки

@paskalnikita · 22.05.2017, 12:54 **[ТС]**

Сообщение от mokojumbot

по моему, очевидно, в какую сторону двигаться от каждой точки

нет, скажем если до точки можно двигаться верх и вправо или вправо и вверх - точки (1;1) (2;2). Тогда мне что, нужно будет два раза перебирать два возможных маршрута и на каком тогда остановиться? Это конечно достаточно простой пример, но а в дальнейшем маршруты могут быть посложнее и какой тогда выбирать? То есть я имею ввиду, когда я двигаюсь к точкам, как лучше сразу идти по у потом по х или сначала по х, а потом по у или поочередно. Как выбрать правильный маршрут в таком случае?

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

@mokojumbot · 22.05.2017, 20:16

paskalnikita, так пока никаких запретов на движение не видно, по этому я и написал самый простой, наверное, пример. "Вверх и вправо" и "вправо и вверх" будут одинаковы.

@moskitos80 · 22.05.2017, 20:31

Т.к. присутствуют правила и стоимость прохождения участков пути - я так понимаю стоит задача поиска кратчайшего пути в лабиринте или типа того? Если так, то рекомендую разобраться с алгоритмом А* (по ссылке довольно подробно разжевано). Но для начала советую разобраться с алгоритмом Дейкстры (поиск кратчайшего пути в графе) т.к. А* это есть почти алгоритм Дейкстры, но плюс функция эвристики. Это не совсем простые алгоритмы, но разобраться с ними стоит.

@paskalnikita · 23.05.2017, 00:22 **[ТС]**

Сообщение от moskitos80

стоит задача поиска кратчайшего пути в лабиринте или типа того

да, верно

Сообщение от moskitos80

алгоритмом Дейкстры

про это читал,но! сделал я что-то такое :

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
 int x_start=x1;
               int y_start=y1;
               int steps=0;
                  while(true){
                        if(x_start<x2){
                           x_start++;
                           steps++;
                        }else if(x_start>x2){
                              x_start--;
                              steps++;
                        }
 
                        if(y_start<y2){
                           y_start++;
                           steps++;
                        }else if(y_start>y2){
                              y_start--;
                              steps++;
                        }
                        if(x_start==x2 && y_start==y2){
                           break;
                        }
                  }
               cout<<"Steps you made:"<<steps;

когда иду из пункта 1 в пункт 2. И теперь такой вопрос : можно ли как-то сделать так, чтобы шаги всегда был случайными? то есть у меня сделано так, что я проверяю х потом у, то есть они чередуются в проверке. А можно сделать как-то так, чтобы маршрут всегда был случайным? То есть, чтобы я мог 4 раза проверить х, а потом 2 у. Или 10 х потом 2 у и 3 снова х. Понимаете?

ValeryS · 23.05.2017, 05:02

paskalnikita, волновой алгоритм не рассматривал?
Вот здесь я объяснял что к чему С чего начать писать игру "Шарики"?
вот описание https://ru.wikipedia.org/wiki/Алгоритм_Ли

@moskitos80 · 23.05.2017, 08:59

Сообщение от paskalnikita

чтобы я мог 4 раза проверить х, а потом 2 у. Или 10 х потом 2 у и 3 снова х

А в чем дело? Функцией random я вижу вы пользоваться умеете

берете ответ от рандома, проверяете на чет/нечет, и в зависимости от этого проверяете свой Х или У.

@paskalnikita · 23.05.2017, 11:17 **[ТС]**

Сообщение от moskitos80

берете ответ от рандома

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

@moskitos80 · 23.05.2017, 11:27

Сообщение от paskalnikita

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

Не совсем понял суть вопроса, но если простого random-а мало, или он кажется не совсем рандомным

, то вот здесь есть функции посерьезнее: random

@paskalnikita · 23.05.2017, 15:18 **[ТС]**

moskitos80, под случайным маршрутом я имею ввиду что-то такое : можно двигаться два шага вправо, один вверх, но можно и сразу 1 вверх 2 вправо, а также 1 вправо 1 вверх 1 вправо.то есть в одну и туже точку можно добраться по-разному. И я хочу сделать так, чтобы при запуске у меня всегда был один из 3-ех вариантов для данного примера. Так понятно? Просто, видимо использовать rand для выбора последовательности шагов - самое разумное решение. Но, тогда получается надо использовать switch для маршрута, я правильно понимаю?

@moskitos80 · 23.05.2017, 16:31

Сообщение от paskalnikita

использовать rand для выбора последовательности шагов - самое разумное решение

Как вариант. Может кто то подскажет что то лучше.

@paskalnikita · 24.05.2017, 00:22 **[ТС]**

Сделал следующим образом, может кому понадобится :

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
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
 
int main()
{
    srand(time(NULL));
    int side;
    cout<<"Tell a size of the side of square:";
    cin>>side;
    if(side>0)
    {
        char **square = new char*[side];
        for (int i = 0; i < side; i++)
        {
            square[i] = new char[side];
        }
        int x1,y1,x2,y2,answer;
 
        cout<<"Do you want to enter coordinates?(1-yes;0-no)";
        cin>>answer;
        if(answer==1)
        {
            cout<<"Enter x1=";
            cin>>x1;
            cout<<"Enter y1=";
            cin>>y1;
            cout<<"Enter x2=";
            cin>>x2;
            cout<<"Enter y2=";
            cin>>y2;
            if(x1>side || y1>side || x2>side || y2 > side)
            {
                cout<<"You entered wrong values of coordinates";
                return 0;
            }
        }
        else
        {
            x1=rand()%side+1;
            y1=rand()%side+1;
 
            x2=rand()%side+1;
            y2=rand()%side+1;
        }
 
        for(int j=side; j>0; j--)
        {
            for(int i=1; i<=side; i++)
            {
                if((i-1)==x1-1 && (j-1)==y1-1)
                {
                    square[i-1][j-1]='+';
                }
                else if((i-1)==x2-1 && (j-1)==y2-1)
                {
                    square[i-1][j-1]='+';
                }
                else
                {
                    square[i-1][j-1]='*';
                }
                //cout<<"("<<i<<";"<<j<<")";
            }
            //cout<<endl;
        }
 
        cout<<"First point has coordinates ("<<x1<<";"<<y1<<")"<<endl;
        cout<<"Second point has coordinates ("<<x2<<";"<<y2<<")"<<endl;
        for(int j=side; j>0; j--)
        {
            for(int i=1; i<=side; i++)
            {
                cout<<square[i-1][j-1]<<" ";
            }
            cout<<endl;
        }
        float dist;
        double x,y;
        if(y1<y2)
        {
            y=y2-y1;
            if(x1<x2)
            {
                x=x2-x1;
            }
            else
            {
                x=x1-x2;
            }
        }
        else
        {
            y=y1-y2;
            if(x1<x2)
            {
                x=x2-x1;
            }
            else
            {
                x=x1-x2;
            }
        }
        dist = sqrt(x*x+y*y);
 
        cout<<"Distance between this two points is "<<dist<<"\n";
 
        //from x1 to x2
        int x_current=x1;
        int y_current=y1;
        int steps=0;
        int random_way;
        while(true)
        {
            random_way=rand()%2;
            switch (random_way)
            {
            case 0:
                if(x_current<x2)
                {
                    x_current++;
                    square[x_current-1][y_current-1]='.';
                    steps++;
                }
                else if(x_current>x2)
                {
                    x_current--;
                    square[x_current-1][y_current-1]='.';
                    steps++;
                }
            case 1:
                if(y_current<y2)
                {
                    y_current++;
                    square[x_current-1][y_current-1]='.';
                    steps++;
                }
                else if(y_current>y2)
                {
                    y_current--;
                    square[x_current-1][y_current-1]='.';
                    steps++;
                }
            }
            if(x_current==x2 && y_current==y2)
            {
                square[x_current-1][y_current-1]='!';
                break;
            }
        }
        cout<<"Steps you made:"<<steps<<"\n";
        cout<<"Way from 1 point to 2 will look like that: \n";
        for(int j=side; j>0; j--)
        {
            for(int i=1; i<=side; i++)
            {
                cout<<square[i-1][j-1]<<" ";
            }
            cout<<endl;
        }
        delete [] square;
    }
    else
    {
        cout<<"Side must be > 0";
    }
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@mokojumbot 160 / 160 / 30 Регистрация: 09.11.2012 Сообщений: 1,008
	22.05.2017, 03:26
	в смысле "как"? зная координаты, по моему, очевидно, в какую сторону двигаться от каждой точки 0

@mokojumbot 160 / 160 / 30 Регистрация: 09.11.2012 Сообщений: 1,008
	22.05.2017, 20:16
	paskalnikita, так пока никаких запретов на движение не видно, по этому я и написал самый простой, наверное, пример. "Вверх и вправо" и "вправо и вверх" будут одинаковы. 0

@moskitos80 442 / 99 / 42 Регистрация: 04.10.2011 Сообщений: 359
	22.05.2017, 20:31
	Т.к. присутствуют правила и стоимость прохождения участков пути - я так понимаю стоит задача поиска кратчайшего пути в лабиринте или типа того? Если так, то рекомендую разобраться с алгоритмом А* (по ссылке довольно подробно разжевано). Но для начала советую разобраться с алгоритмом Дейкстры (поиск кратчайшего пути в графе) т.к. А* это есть почти алгоритм Дейкстры, но плюс функция эвристики. Это не совсем простые алгоритмы, но разобраться с ними стоит. 1

ValeryS Модератор 8979 / 6745 / 921 Регистрация: 14.02.2011 Сообщений: 23,856
	23.05.2017, 05:02
	paskalnikita, волновой алгоритм не рассматривал? Вот здесь я объяснял что к чему С чего начать писать игру "Шарики"? вот описание https://ru.wikipedia.org/wiki/Алгоритм_Ли 1

@paskalnikita 86 / 86 / 30 Регистрация: 12.08.2014 Сообщений: 1,129
	23.05.2017, 15:18 [ТС]
	moskitos80, под случайным маршрутом я имею ввиду что-то такое : можно двигаться два шага вправо, один вверх, но можно и сразу 1 вверх 2 вправо, а также 1 вправо 1 вверх 1 вправо.то есть в одну и туже точку можно добраться по-разному. И я хочу сделать так, чтобы при запуске у меня всегда был один из 3-ех вариантов для данного примера. Так понятно? Просто, видимо использовать rand для выбора последовательности шагов - самое разумное решение. Но, тогда получается надо использовать switch для маршрута, я правильно понимаю? 0