Сколько клеток есть, где фишка может быть после 10 ходов Алины на доске 21×21?

Timofey

29

Чтобы решить эту задачу, давайте разберемся, как фишка может перемещаться на доске 21x21. Фишка может двигаться вправо, влево, вверх и вниз, на одну клетку за один ход. Таким образом, мы можем использовать понятие "шаг" вместо "хода".

Предлагаю использовать рекурсивный подход для решения этой задачи. Предположим, у нас есть функция `count_moves(x, y, n)`, где `x` и `y` - это текущие координаты фишки на доске, а `n` - это количество доступных шагов.

Основная идея этой функции заключается в следующем:
- Если `n` равно 0, то мы достигли максимального числа шагов и возвращаем 1 (у нас есть одна клетка, где фишка может оказаться).
- Если `n` больше 0, мы рассматриваем все возможные направления движения (вправо, влево, вверх, вниз), и для каждого направления рекурсивно вызываем функцию `count_moves` с новыми координатами и `n-1`.

Давайте представим это в виде кода:

\[
\text{{count\_moves}}(x, y, n) = \begin{cases}
1, & \text{если } n = 0 \\
\text{count\_moves}(x + 1, y, n - 1) + \text{count\_moves}(x - 1, y, n - 1) + \text{count\_moves}(x, y + 1, n - 1) + \text{count\_moves}(x, y - 1, n - 1), & \text{если } n > 0
\end{cases}
\]

Теперь мы можем вызвать функцию `count_moves` для заданных значений `x = 10`, `y = 10` и `n = 10`:

\[
\text{count\_moves}(10, 10, 10)
\]