Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 09.07.2021
Сообщений: 78
1

Вывести значения вершин выбранного пути от точки А до точки Б

09.03.2022, 23:51. Показов 735. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Привет. Есть программа, которая считает минимальный путь в матрице. Как в ней вывести значения вершин выбранного пути?
Что-то в формате:
Минимальное суммарное значение нагрузок на путь: 8
Путь: 1 -> 3 -> 1 -> 2 -> 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
#include <iostream>
using namespace std;
 
void minpath(int r, int c, int a[][100])
{
int i,j;
for (i=1;i<r;i++) {
a[i][0]= a[i][0]+a[i-1][0];
}
for (j=1;j<c;j++) {
a[0][j]=a[0][j]+a[0][j-1];
}
for(i=1;i<r;i++) {
for (j=1;j<c;j++) {
if(a[i-1][j] <=a[i][j-1]) {
a[i][j] = a[i][j] + a[i-1][j];
}
else {
a[i][j] = a[i][j]+a[i][j-1];
}
}
cout << "\n";
}
cout << "Строим минимальный путь от точки (0,0):\n";
for(i=0;i<r;i++)
{
for(j=0;j<c;j++) {
cout << a[i][j] << " ";
}
cout << "\n";
}
cout << "Минимальное суммарное значение нагрузок на путь: " << a[r-1][c-1];
}
 
int main() {
int i,j,a[100][100],r,c;
cout << "Построение минимального пути от верхнего левого до правого нижнего угла матрицы:\n";
cout << "Пожалуйста, введите количество строк: ";
cin >> r;
cout << "Пожалуйста, введите количество столбцов: ";
cin >> c;
cout << "Пожалуйста, введите элементы матрицы: \n";
for(i=0;i<r;i++)
{
for (j=0;j<c;j++)
{
cin >> a[i][j];
}
}
 
cout << "Вы ввели следующие элементы: \n";
for(i=0;i<r;i++) 
{
for(j=0;j<c;j++)
{
cout << a[i][j] << " ";
}
cout << "\n";
}
minpath(r,c,a);
return 0;
}
Добавлено через 1 час 51 минуту
Или можно вывести по другому, к примеру ввели матрицу:

1 2 3
1 2 3
1 2 3

Получилась матрица после сложения:

1 3 6
2 4 7
3 5 8

И вывести путь вершин: 1 - 2 - 3 - 5 - 8.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.03.2022, 23:51
Ответы с готовыми решениями:

Даны координаты вершин треугольника, и точки М внутри него, вывести минимальное расстояние от точки М до одной их сторон
всем привет,нужна ваша помощь. задача: даны координаты вершин треугольника, и точки М внутри...

Задача (вывести длину кратчайшего пути от точки до точки.)
Пишу задачу, нужно вывести длину кратчайшего пути от точки до точки. проблема в том, что после...

Поиск кратчайшего пути из точки А до точки В на шахматной доске шагом коня
Всем привет. Я новичек в программировании. Большую сложность вызвала задача в которой необходимо...

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

7
2837 / 2339 / 708
Регистрация: 29.06.2020
Сообщений: 8,655
10.03.2022, 00:49 2
Алгоритм Ли

Добавлено через 17 минут
maxim_lebowskiy, если у вас матрица уже просчитана, и правильно, то отправляйтесь от конечной
точки и на каждом шаге выбирайте ячейку с наименьшим значением, и пока не попадете в точку [0,0].
0
0 / 0 / 0
Регистрация: 09.07.2021
Сообщений: 78
10.03.2022, 01:28  [ТС] 3
SmallEvil, Матрица просчитана, поможете с кодом?
0
2837 / 2339 / 708
Регистрация: 29.06.2020
Сообщений: 8,655
10.03.2022, 04:39 4
Цитата Сообщение от maxim_lebowskiy Посмотреть сообщение
Матрица просчитана
Будем надеятся.

Добавлено через 2 часа 35 минут
Пример корявого на коленках (и немного сонным) написанного кода, для поиска обратного пути, по уже пройденной "волной" матрице.
Просто от лени ввел матрицу масок для проверенных ячеек.
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <stack>
#include <utility>
//#include <queue>
#include <limits>
#include <vector>
 
using namespace std;
typedef pair<int, int> walk;
int off[4][2] = { {0,-1}, {0,+1}, {+1,0}, {-1,0}}; // смещения 
struct FindBack{
    FindBack(int ** field_, int rows_, int cols_){
        field = field_;
        rows = rows_; cols = cols_;
        mask.assign(rows, vector<bool>(cols, false));
    }
    stack<walk> operator()(const walk & from, const walk & to){
        walk step(from), tmp;  // текущий шаг
        stack<walk> path;
        path.push(step); // добавляем координаты ячейки
                         // нужно ли добавлять конечную точку, дело 100500-ое    
        int i,j, min;
        while( step != to ){
            mask[step.first][step.second] = true;
            min = numeric_limits<int>::max();
            for(int k=0; k<4; ++k){
                i = step.first  + off[k][0];
                j = step.second + off[k][1];
                if (i >= 0 && i < rows && j >=0 && j<cols && !mask[i][j])
                    if (field[i][j] <= min){
                        min = field[i][j];
                        tmp.first = i;
                        tmp.second = j;
                        mask[i][j] = true;
                    }
            }
            step = tmp;
            path.push(step);
        }
        return path;
    }
    private:
        int ** field;
        int rows, cols;
        vector<vector<bool>> mask;
};
 
int main()
{
    const int rows = 5, cols = 5;
    int d2array[rows][cols]{
        {1,2,3,4,5},
        {20,15,11,6,7},
        {11,10,9,8,7},
        {12,100,17,100,100},
        {13,14,15,16,17}
    };
    int** mtrx = new int*[rows];
    for (int i=0; i<rows; ++i )
        mtrx[i] = d2array[i];
 
    auto path = FindBack(mtrx, rows, cols)({rows-1,cols-1},{0,0});
    while(!path.empty()){
        const auto s = path.top();
        cout << '[' << s.first <<','<< s.second <<"] : " << d2array[s.first][s.second] << endl;
        path.pop();
    }
    return 0;
}
0
0 / 0 / 0
Регистрация: 09.07.2021
Сообщений: 78
10.03.2022, 11:18  [ТС] 5
SmallEvil, Спасибо в любом случае, но можно как-то мой код преобразовать? Ваш для меня сложный пока-что, мы такое еще не проходили. Ну, когда сможете конечно.
0
2837 / 2339 / 708
Регистрация: 29.06.2020
Сообщений: 8,655
10.03.2022, 13:30 6
Цитата Сообщение от maxim_lebowskiy Посмотреть сообщение
но можно как-то мой код преобразовать?
Я хз, можно конечно и в ваш код добавить поиск обратного пути.

Тогда, под путь как минимум выделять массив размером [rows/2 + rows%2 + cols].
И переписывать из одного корявого кода в еще более корявый, желания совсем нет.

В двух словах как я и написал. Начиная с последней точки движемся к наименьшей соседней ячейке.
Запоминаем ее, повторяем, пока есть соседние ячейки или пока не найдена стартовая..
В вашем случае путь будет однозначно существовать.
И моя битовая маска посещенных ячеек тут как бы лишняя.
0
0 / 0 / 0
Регистрация: 09.07.2021
Сообщений: 78
13.03.2022, 21:49  [ТС] 7
Пытался по координатам сделать путь, не получилось. Если у кого есть время - помогите плиз.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
a[r - 1][c - 1];
    for(i = 0; i<=r;i++) {
      for (j=0;j<=c;j++)
          {
               cout << "(" << r << "," << c << ") <- ";
               if (a[r][c]) --c; else --r;
               if (r == 0 && c == 0)
        {
            cout << "(0,0)\n";
            break;
        }
    }
}
0
2837 / 2339 / 708
Регистрация: 29.06.2020
Сообщений: 8,655
13.03.2022, 22:17 8
Цитата Сообщение от maxim_lebowskiy Посмотреть сообщение
Пытался по координатам сделать путь, не получилось
Что это ???

Вам нужно от текущей точки, a[r - 1][c - 1], найти из всех прилегающих, наименьшую .
Хоть под микроскопом смотри. не вижу этого в вашем коде.
0
13.03.2022, 22:17
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.03.2022, 22:17
Помогаю со студенческими работами здесь

Поиск кратчайшего пути от точки А до точки В
Всем добрый день!)Нужен совет. Реализовал алгоритм для поиска кратчайшего пути от т.А до т.В.,но...

Даны координаты вершин треугольника и координаты точки внутри него. Найти расстояние от данной точки до ближайшей сторон
Задание: Даны координаты вершин треугольника и координаты точки внутри него. Найти расстояние от...

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

Нахождение пути от точки А до точки Б
Ребят, подкиньте идей, как добраться от точки А до точки W. Набросал картинку

Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от данной точки до ближайшей стороны треугольника
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от...

Вывести расстояние от заданной точки до точки пересечения диагоналей прямоугольников
Прямоугольники заданы координатами их вершин. 1)Вывести расстояние от заданной точки до точки...

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


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru