Question

за какое наименьшее число ходов на шахматной доске 2020×1012 конь может попасть из нижней левой клетки доски в диаметрально противоположную правую верхнюю ("конь" ходит буквой Г- 2 клетки в одном направлении + 1 клетка в перпендикулярном направлении)

Answer 1

Ответ:

1012 ходов

Пошаговое объяснение:

Если идти по диоганали 2 вверх 1 вправо, то на 1010 ходу конь будет в клетке (2020;1010) , но нужно в клетку (2020;1012) , а значит нужно сделать ещё 2 хода: 1 вправо-вниз и 1 вправо-вверх. Итого 1010+2=1012 хода.

Answer 2

Для решения данной задачи, можно воспользоваться алгоритмом поиска в ширину (BFS) на шахматной доске. Начнем двигаться конем из нижней левой клетки и будем шаг за шагом исследовать все возможные ходы.

Из каждой клетки можно сделать 8 возможных ходов коня. Начнем с нижней левой клетки и будем двигаться по всем возможным ходам. Важно помнить, что каждый ход увеличивает расстояние до целевой клетки на 3.

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

Исходя из этого, наименьшее число ходов, необходимое для достижения целевой клетки, равно (2020 + 1012) / 2 = 1516.

Таким образом, конь может достичь диаметрально противоположную правую верхнюю клетку на шахматной доске 2020×1012 за 1516 ходов.