Ходы коня
Вам дана сетка 8×8, в которой строки нумеруются от 0 до 7 сверху вниз, а столбцы – от 0 до 7 слева направо. В клетке
(a, b) размещён конь. Конь ходит по правилам стандартного шахматного коня:- Конь перемещается «буквой Г»: делает два шага в одном направлении (по горизонтали или вертикали), а затем поворачивает и делает один шаг перпендикулярно предыдущему направлению.
- Конь не может выйти за границы 8×8.
Каждый ход коня имеет стоимость. Стоимость перемещения коня из позиции в позицию определяется выражением
y⋅r + x⋅c.Учитывая начальную позицию коня
(a, b), требуется вычислить и вывести минимальную стоимость, чтобы добраться из (a, b) до каждой другой клетки в сетке.Напишите программу, которая получает на вход начальное положение коня и выводит минимальную стоимость для каждой клетки сетки.
Входные данные
Во входной строке даны два целых числа
a и b через пробел (0 ≤ a, b ≤ 7), обозначающие начальную позицию коня.Выходные данные
Выведите восемь строк, в каждой из которых содержится восемь целых чисел, разделённых пробелами.
i-ое число в j-ой строке должно соответствовать минимальной стоимости хода из позиции (a, b) в позицию (i, j) на доске 8×8.Пример
Input | Входные данные |
1 1 | 13 11 11 3 17 29 43 53
11 0 13 14 19 18 41 64
11 13 9 5 15 31 45 55
3 14 5 22 23 26 45 72
17 19 15 23 25 43 59 73
29 18 31 26 43 58 69 98
43 41 45 45 59 69 97 123
53 64 55 72 73 98 123 146 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB