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

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

Войти
Регистрация
Восстановить пароль
 
Shevko
0 / 0 / 0
Регистрация: 22.05.2011
Сообщений: 12
#1

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

12.07.2011, 15:52. Просмотров 751. Ответов 3
Метки нет (Все метки)

Задание:

В таблице из 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;
}
А вот дальше не получается

Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.07.2011, 15:52     Поиск путей с минимальной суммой цифр
Посмотрите здесь:

Поиск строки с минимальной суммой элементов - C++
int Min() { int sum_min = 0, index =0; for (int i = 0; i &lt; n; i++) { int sum = 0; for (int j = 0; j &lt; m; j++) ...

В заданной матрице поменять строку с минимальной суммой со строкой с максимальной суммой - C++
помогите с кодом

В целочисленной матрице поменять местами столбец с минимальной суммой со столбцом с максимальной суммой - C++
Дана прямоугольная матрица nxm целых чисел (n,m&lt;10 – ввод с клавиатуры, значения элементов массива в диапазоне – вводятся случайным...

Найти разность между суммой цифр на четных и суммой цифр на нечетных местах - C++
Нужен код для выведения разности между суммой цифр на четных и суммой цифр на нечетных местах. Условия задачи ниже. &quot;Для делимости...

В двумерном N*K массиве целых чисел поменять строку с максимальной суммой элементов со строкой с минимальной суммой элементов. - C++
Массив заполнять случайными числами, кроме случаев, когда это нецелесообразно (прогрессия, лабиринт). -В двумерном N*K массиве целых...

Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). - C++
Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). Вот тут у меня есть код...

Найти строку с минимальной суммой элементов - C++
Найти строку с минимальной суммой элементов. Если таких строк несколько то нужн найти номер первой из них! #include &lt;iostream&gt; ...

Неправильно выводит строчку с минимальной суммой массива - C++
В чём проблема я не очень понимаю // 2.1.cpp: главный файл проекта. #include &quot;stdafx.h&quot; #include &lt;algorithm&gt; #include...

Массив: Найти столбик с минимальной суммой элементов - C++
дано двумерный массив целых чисел, найти столбик с минимальной суммой элементов

Дана Матрица Н(6,5). Найти столбец с минимальной суммой элементов - C++
Дана Матрица Н(6,5). Найти столбец с минимальной суммой элементов Добавлено через 52 секунды не могу сделать подскажите пожалуйста

В целочисленной матрице найти номер столбца с минимальной суммой элементов - C++
С++.дана целочисленная матрица (m,n) Найти номер столбца с минимальной суммой элементов

Неправильно выводит строчку с минимальной суммой элементов строки массива - C++
В чём проблема я не очень понимаю // 2.1.cpp: главный файл проекта. #include &quot;stdafx.h&quot; #include &lt;algorithm&gt; #include...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
12.07.2011, 16:42     Поиск путей с минимальной суммой цифр #2
идея, видимо, в построении бинарного (т.к. движение из каждой точки возможно только в две соседние) дерева на основе этой матрицы и применения к нему алгоритма Дейкстры. и то и другое описано в той же википедии. дерзай.
надеюсь, не усложняю решение задачи)
neske
1474 / 841 / 74
Регистрация: 26.03.2010
Сообщений: 2,889
12.07.2011, 16:54     Поиск путей с минимальной суммой цифр #3
Помню еще такой способ.
Вот, к примеру, у вас дана матрица -
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
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.07.2011, 22:33     Поиск путей с минимальной суммой цифр #4
neske, Идея самая лучшая. Чуть подправлю здесь:

Цитата Сообщение от neske Посмотреть сообщение
Получится так:
9 13 16
11 12 18
11 21 19
Правильно так:
9 13 16
11 12 18
11 20 19
Знаю что это была очепятка.
Yandex
Объявления
12.07.2011, 22:33     Поиск путей с минимальной суммой цифр
Ответ Создать тему
Опции темы

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