Question

С++ Cамый дешёвый путь В каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути). Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Answer 1

Ответ:

#include <iostream>

#include <vector>

using namespace std;

int data[20][20], x, y, minValue = -1;  

void calc(int px, int py, int value){  

  value += data[px][py];

  int temp = data[px][py];

 if(px == x - 1 && py == y - 1) {

      if(value < minValue || minValue == -1)

          minValue = value;

      return;

 }

 data[px][py] = -1;

  if(px + 1 < x && data[px + 1][py] != -1) calc(px + 1, py, value);

  if(py + 1 < y && data[px][py + 1] != -1) calc(px, py + 1, value);

data[px][py] = temp;

}

int main(){

  cin >> x >> y;

  for (int i = 0; i < x; ++i)

      for (int j = 0; j < y; ++j)

         cin >> data[i][j];

calc(0, 0, 0);

 cout << minValue;  

 return 0;

}

Объяснение:

Answer 2

Для решения данной задачи можно использовать динамическое программирование. Создадим двумерный массив dp размером N×M, где dp[i][j] будет представлять минимальный вес еды, который игрок должен отдать, чтобы попасть из клетки (0,0) в клетку (i,j). Заполним этот массив с верхнего левого угла до правого нижнего угла.

Исходные данные: таблица размером N×M с числами.

1. Инициализируем dp[0][0] равным значению в клетке (0,0) таблицы.

2. Заполняем первую строку и первый столбец dp:

   • Для первой строки: dp[0][j] = dp[0][j-1] + значение в клетке (0,j) (так как мы можем перемещаться только вправо).
   • Для первого столбца: dp[i][0] = dp[i-1][0] + значение в клетке (i,0) (так как мы можем перемещаться только вниз).

3. Заполняем остальные ячейки dp[i][j] следующим образом:

   dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + значение в клетке (i,j)

   Мы выбираем минимальный путь из двух возможных: сверху или слева.

4. В конечной ячейке dp[N-1][M-1] будет содержаться минимальный вес еды, необходимый для достижения правого нижнего угла.

Вот пример кода на C++ для решения этой задачи:

cppCopy code
#include <iostream>
#include <vector>

using namespace std;

int findMinimumFood(vector<vector<int>>& table) {
    int N = table.size();
    int M = table[0].size();
    vector<vector<int> > dp(N, vector<int>(M, 0));

    dp[0][0] = table[0][0];

    // Заполняем первую строку и первый столбец
    for (int i = 1; i < N; i++) {
        dp[i][0] = dp[i - 1][0] + table[i][0];
    }
    for (int j = 1; j < M; j++) {
        dp[0][j] = dp[0][j - 1] + table[0][j];
    }

    // Заполняем остальные ячейки
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + table[i][j];
        }
    }

    return dp[N - 1][M - 1];
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> table(N, vector<int>(M));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> table[i][j];
        }
    }

    int minimumFood = findMinimumFood(table);
    cout << "Минимальный вес еды: " << minimumFood << " кг" << endl;

    return 0;
}

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