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

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

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

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

22.11.2015, 09:43. Просмотров 197. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.11.2015, 09:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Минимальный путь от левой верхней клетки до правой нижней (C++):

Минимальный путь из левой верхней в правую нижнюю клетку таблицы. - C++
Не могу понять в чем ошибка...помогите. Химическая тревога (Время: 1 сек. Память: 16 Мб Сложность: 50%) Произошло радиоактивное...

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

менять местами символы в массиве в нижней и верхней четверти - C++
суть такова. есть код, который созддает массив случайных чисел заданного размера. диагонали равны 0. нужно просто поменять местами верхнюю...

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

Поменять местами наибольшие элементы в верхней и нижней половинах матрицы - C++
В матрице A( n- строк, m- столбцов; n- четное) поменять местами наибольшие элементы в ее верхней и нижней половинах. Для поиска индексов...

Поменять местами наибольшие элементы в верхней и нижней половинах матрицы (подпрограммы) - C++
В матрице A( n- строк, m- столбцов; n- четное) поменять местами наибольшие элементы в ее верхней и нижней половинах. Для поиска индексов...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.11.2015, 09:43
Привет! Вот еще темы с ответами:

Определить, в какой из половин матрицы (верхней или нижней) больше нулевых элементов - C++
Для матрицы А(n строк, m столбцов, n-четное) определить, в какой из ее половин (верхней или нижней) больше нулевых элементов. Для подсчета...

Нули массива, размещены в левой и верхней четвертях матрицы - C++
Сохранить нулевые элементы массива, которые размещены в левой и верхней четвертях матрицы. Как я понял, четверти определяются благодаря...

Диапазон положительных чисел задан нижней и верхней границами. Распечатать все простые числа, лежащие в указанном диапазоне. - C++
Program pr11_1; uses crt; var chislo,delite1,e,b,flag1,flag2:longint; {===============================} procedure swap_(var...

Сумма цифр правой и левой частей (ошибки) - C++
Хоть убейте не могу понять где ошибки. #include &lt;iostream&gt; #include &lt;cmath&gt; using namespace std; int main() { double N,...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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