Question

С++ Шашку — в дамки

На шахматной доске (8×8) стоит одна белая шашка. Сколькими она может пройти в дамки?

(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

Входные данные

Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

Выходные данные

Вывести одно число — количество путей в дамки.

Примеры

Ввод

Вывод

3 7

2

1 8

1

3 6

4

Answer 1

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

#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. Если Вам ответ, отметьте его как лучший и жмякните на " " . Это мотивирует продолжать давать ответы дальше.