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

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

Восстановить пароль Регистрация
 
Shevko
0 / 0 / 0
Регистрация: 22.05.2011
Сообщений: 12
12.07.2011, 15:52     Поиск путей с минимальной суммой цифр #1
Задание:

В таблице из 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++
C++ В двумерном N*K массиве целых чисел поменять строку с максимальной суммой элементов со строкой с минимальной суммой элементов.
Найти строку с минимальной суммой элементов C++
C++ Заменить все столбцы на столбец с минимальной суммой элементов (Класс)
C++ Массив: Найти столбик с минимальной суммой элементов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
12.07.2011, 16:42     Поиск путей с минимальной суммой цифр #2
идея, видимо, в построении бинарного (т.к. движение из каждой точки возможно только в две соседние) дерева на основе этой матрицы и применения к нему алгоритма Дейкстры. и то и другое описано в той же википедии. дерзай.
надеюсь, не усложняю решение задачи)
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,689
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++
 Аватар для valeriikozlov
4660 / 2486 / 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     Поиск путей с минимальной суммой цифр
Ответ Создать тему
Опции темы

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