UniLecs #Task. Knight Move

Albert Davletov
UniLecs
Published in
2 min readJan 20, 2020

Задача: дана прямоугольная доска 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 — уменьшается, что является движением влево-вниз.

Реализация

C#

https://gist.github.com/unilecs/7ae901657bdb193bed03f09769e407ea

Play-test

https://dotnetfiddle.net/qH1lRV

--

--