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

Минимальный путь от левой верхней клетки до правой нижней - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ В строке s1 поменять местами первое и второе слово и скопировать в s2 http://www.cyberforum.ru/cpp-beginners/thread1588715.html
Здравствуйте . Как в строке s1, поменять местами первое и второе слово и скопировать в s2? include <iostream.h> include<string.h> int main ( ) { s1 = "Hello world"; s2;
C++ Основные типы данных, объявление и инициализация переменных ребятки, попробуйте 1) Объявить в программе переменные и константы (выбор обосновать) для хранения следующих данных: а) число , б) возраст человека, в) масса электрона, г) расстояние между... http://www.cyberforum.ru/cpp-beginners/thread1588707.html
Основные типы данных C++
1) Объявить в программе переменные и константы (выбор обосновать) для хранения следующих данных: а) площадь произвольного цилиндра, 8 б) масса Солнца, в) масса планеты Солнечной системы, г)...
C++ Ввод/вывод значений элементов массива
Есть двумерный QVector "mass" Заполненный объектами класса "МОЙ_КЛАСС" и ограничен размерами n*n. Объекты класса "МОЙ_КЛАСС" имеют свойства "x" и "y". Если во время заполнения массива (допустим...
C++ Найти сумму элементов массива, цифры записи которых образуют возрастающую последовательность http://www.cyberforum.ru/cpp-beginners/thread1588643.html
Найти сумму элементов целочисленного массива, цифры записи которых образуют возрастающую последовательность и которые расположены между максимальным и минимальным элементами (включая сами элементы)....
C++ Ошибка компоновщика: error LNK2019: ссылка на неразрешенный внешний символ Конвертировал, конвертировал, да не переконвертировал. 180 ошибок убрал. остались только эти: error LNK2019: ссылка на неразрешенный внешний символ "void __cdecl clear_console(int *,int *)"... подробнее

Показать сообщение отдельно
Marie05
0 / 0 / 0
Регистрация: 22.11.2015
Сообщений: 1

Минимальный путь от левой верхней клетки до правой нижней - C++

22.11.2015, 09:43. Просмотров 195. Ответов 0
Метки (Все метки)

Нужно определить минимальный путь, как можно добраться от верхней левой клетки до правой нижней. Задаётся поле массивом NxM (где N - кол-во строк, а M - кол-во столбиков). Проходить по клеткам можно либо вниз, либо вправо. И при попадании на клетку к общему минимальному пути добавляется число, которое было записано в этой клетке.
Например:
2 3
1 6 7
2 8 4
Начинаем с верхней левой клетке. Значит, пока что результат = 1. Дальше можем пойти либо вправо (к 6), либо вниз(2). Естественно идём вниз, т.к. ищем минимальный путь. Уже ми. путь равен 1+2=3. Дальше вниз мы пойти уже не можем, идём вправо. 1+2+8=11. И на последнюю клетку тоже вправо. 1+2+8+4=15.
Итак, мин. путь = 15.
Решать эту задачу я хочу используя дин. прог.
Сначала использую тривиальную задачу, указывая, что для левой верхней клетки мин.путь = 0. А потом задаю формуу в цикле, которая выбирает оптимальный вариант из "пойти вправо или вниз" и прибавляет число, которое находится на данной клетке. Но при этом программа не работает корректно, выдаёт совершенно неправильный результат. (например на выше приведённом примере выдаст , что мин. путь равен 4, но это ведь совсем не так!)
В чём проблема?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(int argc, char* argv[]) {
    int N, M;
    cin >> N >> M;
    vector<vector<int> > arr(N , vector<int>(M));
    vector<vector<int> > res(N, vector<int>(M));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            cin >> arr[i][j];
    }
 
    res[0][0] = arr[0][0];
 
    for (int i = 1; i < N ; i++) {
        for (int j = 1; j < M; j++) 
            res[i][j] = min(res[i][j-1], res[i-1][j]) + arr[i][j];
    }
 
    cout << res[N-1][M-1];
 
    system("pause");
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru