задача
Cамый дешёвый путь
В каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).
Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.
Входные данные
Вводятся два числа N и M — размеры таблицы 1⩽N⩽20,1⩽M⩽20. Затем идёт N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).
Выходные данные
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.
Мой код
#include <iostream>
#include <vector>
int main() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> a(n, std::vector<int>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
std::cin >> a[i][j];
for (int i = 1; i < n; i++) {
a[i][0] += a[i - 1][0];
a[0][i] += a[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
int a1 = a[i - 1][j];
int a2 = a[i][j - 1];
a[i][j] += std::min(a1, a2);
}
}
std::cout << a[n - 1][m - 1];
}
Средний
