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;

}

Объяснение: