UniLecs #Task. Knight Move
Задача: дана прямоугольная доска N×M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке, конь не может выходить за границы доски.
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
Входные данные: N и M, где (1 ⩽ N,M ⩽ 15).
Вывод: количество способов добраться конём до правого нижнего угла доски.
Примеры:
1. N = M = 4;
Output: 2;
2. N = 15, M = 14;
Output: 7884330
Разбор
Решим задачу методом динамического программирования.
Целевая функция — F(i, j) — количество путей коня из начальной клетки в клетку (i, j).
В клетку (i, j) можно прийти из четырех клеток: (i+1, j−2), (i−1, j−2), (i−2, j−1), (i−2, j+1), поэтому
F(i, j) = F(i+1, j−2) + F(i−1, j−2) + F(i−2, j−1) + F(i−2, j+1).
Необходимо двумерный список F заполнить значениями по этой формуле таким образом, чтобы при вычислении нового значения в клетке были вычислены значения в тех четырех клетках, которые необходимы для вычисления значения в клетке (i,j).
Таблицу будем заполнять по диагоналям идущим влево-вниз, то есть сначала заполняется значение в левом верхнем углу, затем — значения по диагонали длиной 2, соседней с угловой клеткой, затем по диагонали длиной 3, соседней с данной диагональю длиной 2 и т. д. Дополнительная каемочка будет иметь размер 2 столбца слева и 2 строки сверху, 1 строка снизу и 1 столбец справа. Поэтому начальная клетка будет иметь координату (2, 2) и F(2, 2) = 1, а конечная клетка будет (n+1, m+1) и необходимо найти F(n+1, m+1).
В этом решении starti и startj — номера начальной клетки для цикла по диагонали. Эта начальная клетка перемещается сначала по верхней стороне прямоугольника, поэтому startj увеличивается на 1, затем по правой стороне прямоугольника, тогда starti увеличивается на 1. Внутренний цикл — это цикл по диагонали, в этом цикле i увеличивается, а j — уменьшается, что является движением влево-вниз.
Реализация
https://gist.github.com/unilecs/7ae901657bdb193bed03f09769e407ea
