Question

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.

Answer 1

Ответ:

#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;

}

Объяснение: