Кратчайший путь коня (Knight Shortest Path)

Условие:

Дана шахматная доска размера N × N.

В клетке (x1, y1) находится шахматный конь. Нужно найти самый короткий маршрут до клетки (x2, y2).

Некоторые клетки заблокированы и обозначены символом "#". На такие клетки ходить нельзя.

Конь ходит стандартным шахматным ходом:

(+2, +1), (+2, -1), (-2, +1), (-2, -1),
(+1, +2), (+1, -2), (-1, +2), (-1, -2)

Если путь существует, нужно вернуть массив координат маршрута от старта до финиша включительно.

Если пути нет, нужно вернуть null.

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

board — массив строк размера N
x1, y1 — координаты стартовой клетки
x2, y2 — координаты конечной клетки

Координаты считаются с нуля.

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

Массив координат пути: [[x1, y1], ..., [x2, y2]]

или

null

Ограничения:

1 <= N <= 100
board.length == N
board[i].length == N
0 <= x1, y1, x2, y2 < N
board[x1][y1] != "#"
board[x2][y2] != "#"

Пример:

Вход:

board = [
  "...",
  "...",
  "..."
]

x1 = 0
y1 = 0
x2 = 1
y2 = 2

Выход:

[[0, 0], [1, 2]]