Поиск путей с минимальной суммой цифр

@Shevko · Регистрация: 22.05.2011

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

Задание:

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

Ввод
В первой строке находится число N (2 ≤ N ≤ 250). В следующих N строках содержатся по N цифр без пробелов.
Вывод
Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус – что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Пример ввода
3
943
216
091
Пример вывода
#--
###
--#

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

Вот, написал код для заполнения массива из N по N элементов:

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
#include <iostream>
#include <time.h>
using namespace std;
 
int main()
{
int **m;
int N;
cout<<"Vvedite N:"<<endl;
cin>>N;
 
m=new int *[N];
for (int i=0;i<N;i++)
{
    m[i]=new int [N];
}
 
srand(time(NULL));
 
for (i=0;i<N;i++)
{
for (int j=0;j<N;j++)
    m[i][j]=rand()%10;
}
 
for (i=0;i<N;i++)
{
for (int j=0;j<N;j++)
    cout<<m[i][j];
cout<<endl;
}
 
 
return 0;
}

А вот дальше не получается

Заранее спасибо!

@Paporotnik · 12.07.2011, 16:42

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

@neske · 12.07.2011, 16:54

Помню еще такой способ.
Вот, к примеру, у вас дана матрица -
943
216
091

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

C++
1
mas1[i][j] = std::min(mas1[i - 1][j], mas1[i][j - 1]) + mas[i][j];

Получится так:
9 13 16
11 12 18
11 21 19

Теперь остается найти сам путь. Идем из клетки (N, N) в клетку (1, 1), сравнивая (i - 1, j) и (i, j - 1) элементы.

valeriikozlov · 12.07.2011, 22:33

neske, Идея самая лучшая. Чуть подправлю здесь:

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

Получится так:
9 13 16
11 12 18
11 21 19

Правильно так:
9 13 16
11 12 18
11 20 19
Знаю что это была очепятка.

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@Paporotnik 385 / 229 / 12 Регистрация: 06.07.2011 Сообщений: 512
	12.07.2011, 16:42
	идея, видимо, в построении бинарного (т.к. движение из каждой точки возможно только в две соседние) дерева на основе этой матрицы и применения к нему алгоритма Дейкстры. и то и другое описано в той же википедии. дерзай. надеюсь, не усложняю решение задачи) 1