Question

С++ Cамый дешёвый путьВ каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.Входные данныеВводятся два числа N и M — размеры таблицы 1≤N≤20,1≤M≤20. Затем идёт N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).Выходные данныеВыведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.ПримерыВводВывод5 51 1 1 1 13 9 9 9 91 1 1 1 12 2 2 2 11 1 1 1 111

Answer 1

Ответ:

#include <iostream>

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;

}

Объяснение:

Я сделал это задание с помощью рекурсии. Функция бесконечно вызывает сама себя и ищет наиболее оптимальный вариант. Фактически это просто подбор, но более сложно реализованный.

P. s. Если Вам помог ответ, отметьте его как лучший и жмякните на "Спасибо", пожалуйста. Это мотивирует продолжать давать ответы дальше.

Answer 2

Ответ:

#include <cstdio>

#include <algorithm>

using namespace std;

int a[30][30], n, m;

int main() {

  scanf(" %d %d", &n, &m);

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

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

        scanf(" %d", &a[i][j]);

  for(int i = 1; i < m; i++) a[0][i] += a[0][i - 1];

  for(int i = 1; i < n; i++) a[i][0] += a[i - 1][0];

  for(int i = 1; i < n; i++)

     for(int j = 1; j < m; j++)

        a[i][j] += min(a[i - 1][j], a[i][j - 1]);

  printf("%d", a[n - 1][m - 1]);

  return 0;

}

Объяснение:

Answer 3

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

В этом процессе будем использовать следующее рекуррентное соотношение для заполнения dp:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

где grid[i][j] - это штраф за прохождение через клетку (i, j), dp[i-1][j] - минимальный вес пути до клетки выше, и dp[i][j-1] - минимальный вес пути до клетки слева. Мы выбираем минимум из этих двух путей, так как нам нужно выбрать наименьший вес пути.

Начнем с заполнения первой строке и первого столбца массива dp:

cppCopy code
dp[0][0] = grid[0][0];
for (int i = 1; i < N; i++) {
    dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j = 1; j < M; j++) {
    dp[0][j] = dp[0][j-1] + grid[0][j];
}

Затем, заполним остальную часть массива dp используя рекуррентное соотношение:

cppCopy code
for (int i = 1; i < N; i++) {
    for (int j = 1; j < M; j++) {
        dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
    }
}

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

Вот полный код на C++:

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

using namespace std;

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

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

    vector<vector<int>> dp(N, vector<int>(M));
    dp[0][0] = grid[0][0];

    for (int i = 1; i < N; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }

    for (int j = 1; j < M; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout << dp[N-1][M-1] << endl;
    return 0;
}

Этот код считывает входные данные, заполняет массив dp, и выводит минимальный вес еды.