C/C++

Задача C++. Шашку - в дамки

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

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

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

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

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

Вывести одно число — количество путей в дамки.
Vladimir Lisnik
Vladimir Lisnik
76 
 int x, y, t[9][10] = {0};

cin >> x >> y;

t[y][x] = 1;

for (int i = y + 1; i
ВР
Вячеслав Руденко
90 131
Лучший ответ
Евгений Кутьков Нет ли тут какого-нибудь треугольника Паскаля?
В смысле?
Перебором всех ходов что-ле??!
Argint Ojovan
Argint Ojovan
91 288
Для решения задачи можно использовать рекурсивный подход. Давайте определим функцию, которая будет считать количество путей для текущего положения шашки на доске. Функция должна принимать текущие координаты шашки (x, y) и возвращать количество путей.

Когда шашка достигает верхней горизонтали, мы заканчиваем поиск и возвращаем 1 (так как мы нашли один путь).

В противном случае, мы можем пойти на одну клетку вверх-вправо или вверх-влево, если там нет других фигур. Если мы выходим за границы доски, или если на следующей клетке стоит другая фигура, мы не рассматриваем этот путь.

Для решения задачи нужно вызвать эту функцию с начальными координатами шашки и вернуть полученное количество путей.

Ниже приведен код на C++ для решения данной задачи:

 #include  

using namespace std; 

 

int count_paths(int x, int y) { 

    // если шашка достигла верхней горизонтали, возвращаем 1 

    if (y == 8) return 1; 

 

    int paths = 0; 

 

    // пытаемся пойти вверх-вправо 

    if (x < 8 && y < 8 && (x + y) % 2 != 0) { 

        paths += count_paths(x + 1, y + 1); 

    } 

 

    // пытаемся пойти вверх-влево 

    if (x > 1 && y < 8 && (x + y) % 2 != 0) { 

        paths += count_paths(x - 1, y + 1); 

    } 

 

    return paths; 

} 

 

int main() { 

    int x, y; 

    cin >> x >> y; 

    cout
Сергей Крушинский
Сергей Крушинский
6 592

Похожие вопросы