ナイトの移動
8×8 のグリッドが与えられています。グリッドの行は上から下へ 0 から 7、列は左から右へ 0 から 7 の番号が振られています。ナイトはセル (a, b) に配置されており、通常のチェスのナイトと同様の動きをします。具体的には次のとおりです。
- ナイトは「L」の形に動き、縦方向または横方向に 2 マス進んでから、その進行方向と直角になる方向に 1 マス進みます。
- グリッドの範囲 (8×8) から外には移動できません。
ナイトが位置 から位置 へ移動するときのコストは、次の式で与えられます:
初期状態としてナイトがセル (a, b) にいるとき、ナイトが (a, b) からグリッド上のすべてのセルへ移動するために必要となる「最小コスト」を求めてください。プログラムでは、ナイトの初期位置 (a, b) を入力として受け取り、グリッドのそれぞれのセルに移動する際の最小コストを出力します。
入力
1 行に、ふたつの整数 a と b (0 ≤ a, b ≤ 7) が空白区切りで与えられ、これはナイトの初期位置を表します。
出力
8 行を出力し、それぞれの行には 8 つの整数を空白区切りで出力してください。j 行目の i 番目の整数は、ナイトが位置 (a, b) から (i, j) へ移動するのに必要な最小コストを表します。
例
入力 | 出力 |
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