В
Все
М
Математика
О
ОБЖ
У
Українська мова
Х
Химия
Д
Другие предметы
Н
Немецкий язык
Б
Беларуская мова
М
Музыка
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
У
Українська література
Р
Русский язык
Ф
Французский язык
П
Психология
О
Обществознание
А
Алгебра
М
МХК
Г
География
И
Информатика
П
Право
А
Английский язык
Г
Геометрия
Қ
Қазақ тiлi
Л
Литература
И
История
Самира271106
Самира271106
03.03.2022 18:38 •  Информатика

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.

Показать ответ
Ответ:
Znanija027
Znanija027
25.04.2021 18:20

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

}

Объяснение:

0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота