Продолжаю решать задачи на веб-сервисе «CodeRun» от «Яндекса». Я подробно описал этот веб-сервис в прошлом посте. В этом посте я хочу описать решение еще одной задачи из группы «легких». Задача называется «Ход конем».

Формулировка задачи

В левом верхнем углу прямоугольной доски размерами N × M (каждый из этих размеров является целым числом клеток в диапазоне от 1 до 50, включая границы) находится шахматный конь. В этой задаче конь может ходить только вправо или вниз (две клетки вправо и одна вниз; две клетки вниз и одна вправо). Найти общее количество возможных путей коня до нижнего правого угла доски. Путь нулевой длины считается корректным маршрутом.

Неоднозначность с запятой

Как обычно, я постарался сократить и по возможности упростить оригинальную формулировку задачи. В оригинале автор задачи использует математическое обозначение, которое ввело меня в заблуждение:

1 ≤ N, M ≤ 50

Поначалу я думал, что это выражение интерпретируется как два неравенства:

(1 ≤ N) и (M ≤ 50)

Но оказалось, что правильная интерпретация следующая:

(1 ≤ N ≤ 50) и (1 ≤ M ≤ 50)

Я не математик и не смог найти какого-то математического стандарта по этому поводу. В интернетах пишут, что такое сокращение с запятой используют для экономии места, когда условия задачи излагаются на бумаге. Сомневаюсь, что есть смысл использовать такие двусмысленные сокращения в вебе, где места предостаточно.

Решение

После решения задачи из предыдущего поста мне было очевидно, что при решении данной задачи можно использовать те же приемы.

(При поиске решения попалась даже более точная фраза, описывающая понятие «динамического программирования» — рекуррентное соотношение. То есть нужно найти это самое рекуррентное соотношение [если оно существует] и на его основе построить алгоритм решения задачи. Хотя в интернетах мне возразили, что динамическое программирование — это всё-таки нечто большее, чем просто поиск рекуррентного соотношения. Буду вникать дальше.)

Для данной задачи опять строим вспомогательную двумерную таблицу, по размерам совпадающую с размерами исходной доски, по которой ходит конь.

Что означает условие «путь нулевой длины считается корректным маршрутом»? Я думаю, это значит, что при доске размерами 1 × 1 программа должна вернуть значение 1. Получается, что даже если коню некуда пойти, один маршрут у него всегда есть — достаточно остаться на месте.

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

Например, возьмем классическую шахматную доску 8 × 8 и попробуем заполнить ее описанным способом.

1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 1 0 0 1 0 0 0
0 0 0 2 0 0 1 0
0 0 1 0 0 3 0 0
0 0 0 0 3 0 0 4
0 0 0 1 0 0 6 0
0 0 0 0 0 4 0 0

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

Красным цветом отмечены клетки доски, в которые конь может попасть, а число в этих клетках обозначает количество возможных путей коня в эту клетку.

Вот несколько примеров для тестирования:

1 × 1       1
2 × 3       1
3 × 2       1
3 × 3       0
4 × 4       2
6 × 8       4
8 × 8       0
31 × 34     293'930

Видно, что увеличение размеров доски ничего не гарантирует. Важен не только размер доски, но и ее форма.

Код программы на языке C++

#include <iostream>
#include <vector> // для std::vector

int main()
{
    // получить размеры доски,
    // по условиям задачи каждый размер — в диапазоне [1..50]
    int N{};
    int M{};
    std::cin >> N;
    std::cin >> M;

    // составить таблицу количеств путей к каждой клетке доски
    std::vector<std::vector<int>> paths(N, std::vector<int>(M, 0));
    paths[0][0] = 1; // по условиям задачи
    for (int r{}; r < N; r++)
    {
        for (int c{}; c < M; c++)
        {
            if ((r - 1) >= 0 && (c - 2) >= 0) // ход слева существует
            {
                paths[r][c] = paths[r - 1][c - 2];
            }
            if ((r - 2) >= 0 && (c - 1) >= 0) // ход сверху существует
            {
                paths[r][c] += paths[r - 2][c - 1];
            }
        }
    }

    // вывести количество путей коня в правый нижний угол доски
    std::cout << paths[N - 1][M - 1] << '\n';

    return 0;
}

Выводы

В целом постфактум решение задачи кажется легким. Однако, мне пришлось потратить пару часов на ее обдумывание. Наверное, тут имеет значение опытность в применении алгоритмов.