The Knight Moves
You are given an 8x8 grid where the rows are numbered from 0 to 7 from top to bottom, and the columns are numbered from 0 to 7 from left to right. A knight is positioned at cell
(a, b) on the grid. The knight can move according to the standard chess knight rules, which are as follows:- The knight can move in an
Lshape, taking two steps in one direction (horizontally or vertically) and then one step perpendicular to the previous direction.
- The knight cannot move outside the boundaries of the 8x8 grid.
Each knight move has a cost. The cost of moving the knight from position
y⋅r + x⋅c.Given the initial position of the knight at cell
(a, b), your task is to calculate and output the minimum cost required to move the knight from position (a, b) to every other cell on the grid.Write a program that takes the initial position of the knight and outputs the minimum cost for each cell on the grid.
Input
The input consists of a single line containing two space-separated integers,
a and b (0 ≤ a, b ≤ 7), representing the initial position of the knight.Output
Output eight lines, each containing eight space-separated integers. The
i-th integer in the j-th line represents the minimum cost required to move the knight from position (a, b) to position (i, j) on the 8x8 grid.Examples
Input | Output |
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