Question

Шашку — в дамки На шахматной доске (8×8) стоит одна белая шашка. Сколькими способами она может пройти в дамки? (Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.) Входные данные Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка. Выходные данные Вывести одно число — количество путей в дамки. Примеры Ввод Вывод 3 7 2 1 8 1 3 6 4 на c++

Answer 1

Ответ:

Объяснение:

#include <iostream>

#include <cassert>

using namespace std;

int wh(int x, int y) {

   assert(y <= 8&&y>=1&&x>=1&&x<=8);

   if (y == 8) {

       return 1;

   }

   if(x==1)

       return wh(x+1, y+1);

   else if (x==8)

       return wh(x - 1, y + 1);

   else

       return wh(x - 1, y + 1) + wh(x + 1, y + 1);

}

int main()

{

   int x,y;

   cin >> x>>y;

   cout<<wh(x, y );

   return 0;

}

Answer 2

Для решения этой задачи вам нужно воспользоваться динамическим программированием. Мы можем создать двумерный массив размером 8x8, где каждая ячейка [i][j] будет представлять количество способов, которыми шашка может дойти до этой клетки.

Изначально, установите все элементы массива в 0, кроме той клетки, где стоит шашка. Затем начните заполнять массив, двигаясь по доске сверху вниз и слева направо. Для каждой клетки [i][j] количество способов можно вычислить, как сумму количества способов из клеток [i+1][j-1] и [i+1][j+1], если эти клетки существуют и находятся в пределах доски.

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

cppCopy code
#include <iostream>
using namespace std;

int main() {
    int board[8][8] = {0};
    int row, col;

    // Ввод начальной позиции шашки
    for (int i = 0; i < 3; i++) {
        cin >> col >> row;
        board[8 - row][col - 1] = 1;
    }

    // Заполнение массива
    for (int i = 6; i >= 0; i--) {
        for (int j = 0; j < 8; j++) {
            if (board[i][j] == 1) {
                if (j > 0) board[i + 1][j - 1]++;
                if (j < 7) board[i + 1][j + 1]++;
            }
        }
    }

    // Суммируем способы для верхней горизонтальной строки
    int total = 0;
    for (int j = 0; j < 8; j++) {
        total += board[0][j];
    }

    cout << total << endl;

    return 0;
}

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