rows × cols, строки и столбцы нумеруются с нуля, строка 0 — верхняя. Конь стоит в клетке (row, col). Он ходит буквой «Г»: на 2 клетки по одной оси и на 1 по другой, не выходя за доску.
Нужен маршрут, при котором конь побывает в каждой клетке ровно один раз (стартовая уже посещена, возвращаться в неё нельзя). Верните доску, где в каждой клетке записан номер шага, на котором конь в неё пришёл: 0 — старт, затем 1, 2 и так далее до rows · cols - 1.
Маршрутов может быть несколько, поэтому ответ определён правилом. Конь перебирает ходы строго в таком порядке:
| № | Ход |
|---|---|
| 1 | на 2 вверх, на 1 влево |
| 2 | на 1 вверх, на 2 вправо |
| 3 | на 2 вниз, на 1 вправо |
| 4 | на 1 вниз, на 2 влево |
| 5 | на 2 вверх, на 1 вправо |
| 6 | на 1 вниз, на 2 вправо |
| 7 | на 2 вниз, на 1 влево |
| 8 | на 1 вверх, на 2 влево |
Из текущей клетки он идёт первым по порядку ходом в ещё не посещённую клетку; если дальше ходов нет, а обход не закончен, он отступает на шаг назад и пробует следующий по порядку ход. Верните первый полный маршрут, найденный так. Иначе говоря, из всех маршрутов нужен тот, у которого последовательность номеров ходов лексикографически наименьшая.
Если обойти доску нельзя, верните доску с 0 в стартовой клетке и -1 во всех остальных.rows=3, cols=4, row=0, col=0 → [[0, 3, 6, 9], [11, 8, 1, 4], [2, 5, 10, 7]]
Из угла конь сначала пробует ходы 1 и 2 — оба уводят за доску, третий ведёт в (2, 1). Продолжая так и отступая из тупиков, он находит обход всех 12 клеток; в клетке записан номер шага, на котором конь в неё пришёл.
rows=3, cols=3, row=1, col=1 → [[-1, -1, -1], [-1, 0, -1], [-1, -1, -1]]
Из центра доски 3 × 3 конь не может сделать ни одного хода, обхода нет: в стартовой клетке 0, в остальных -1.
rows=1, cols=1, row=0, col=0 → [[0]]
Единственная клетка уже посещена — обход готов.
rows=3, cols=4, row=0, col=0
[[0, 3, 6, 9], [11, 8, 1, 4], [2, 5, 10, 7]]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 55 тестов на сервере, включая скрытые.