Жадные алгоритмы

Пронумеруем все строчки и все столбцы числами от 1 до 100. Тогда нам нужно попасть из клетки (1, 1) в клетку (100, 100). За каждый ход коня одна координата меняется на 1 (+1 или -1), а вторая на 2 (+2 или -2). Будем жадно прыгать к клетке (100, 100). Сначала в клетку (2, 3), потом в (4, 4). Будем продолжать такие прыжки по 2. Тогда получим последовательность клеточек:

(1, 1) -> (4, 4) -> (7, 7) -> …-> (3k + 1, 3k + 1) -> (3(k + 1) + 1, 3(k + 1) + 1) -> ...

Заметим, что закончим мы именно в клетке (100, 100), так как мы побываем на всех клетках вида (3k + 1, 3k + 1), а число 100 представляется в таком виде (дает остаток 1 при делении на 100).

Нам понадобилось ходов.

Проверим оценкой, что наш жадный алгоритм дал лучший результат. За один ход коня сумма координат клетки меняется не более, чем на 3. Тогда, чтобы из суммы 2 получить сумму 200, нужно как минимум ходов.