Cамый дешёвый путь
В каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).
Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.
Входные данные
Вводятся два числа N и M — размеры таблицы 1≤N≤20,1≤M≤20. Затем идёт N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).
Выходные данные
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.
Примеры:
Ввод
5 5
1 1 1 1 1
3 9 9 9 9
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
Вывод
11
Решите, пожалуйста, с помощью двумерных массивов.
Библиотеки iostream, vector.
В каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).
Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.
Входные данные
Вводятся два числа N и M — размеры таблицы 1≤N≤20,1≤M≤20. Затем идёт N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).
Выходные данные
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.
Примеры:
Ввод
5 5
1 1 1 1 1
3 9 9 9 9
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
Вывод
11
Решите, пожалуйста, с помощью двумерных массивов.
Библиотеки iostream, vector.
Answers & Comments
Ответ:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int x, y;
cin >> x >> y;
vector<vector<int> > t(x, vector<int> (y));
for (int i = 0; i < x; ++i){
for (int j = 0; j < y; ++j){
int mark;
cin >> mark;
t[i][j] = mark;
}
}
for (int i = 1; i < y; ++i){
t[0][i] += t[0][i - 1];
}
for (int i = 1; i < x; ++i){
t[i][0] += t[i - 1][0];
}
for (int i = 1; i < x; ++i){
for (int j = 1; j < y; ++j){
t[i][j] += min(t[i - 1][j], t[i][j - 1]);
}
}
cout << t[x - 1][y - 1] << endl;
}
Объяснение: