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

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

Восстановить пароль Регистрация
 
Marie05
0 / 0 / 0
Регистрация: 22.11.2015
Сообщений: 1
22.11.2015, 09:43     Минимальный путь от левой верхней клетки до правой нижней #1
Нужно определить минимальный путь, как можно добраться от верхней левой клетки до правой нижней. Задаётся поле массивом 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.11.2015, 09:43     Минимальный путь от левой верхней клетки до правой нижней
Посмотрите здесь:

Диапазон положительных чисел задан нижней и верхней границами. Распечатать все простые числа, лежащие в указанном диапазоне. C++
Поменять местами элементы матрицы, расположенные в верхней и нижней четвертях C++
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N C++
C++ Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
Поменять местами наибольшие элементы в верхней и нижней половинах матрицы C++
C++ Поменять местами наибольшие элементы в верхней и нижней половинах матрицы (подпрограммы)
Определить, в какой из половин матрицы (верхней или нижней) больше нулевых элементов C++
C++ Нули массива, размещены в левой и верхней четвертях матрицы

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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