D - Root M Leaper Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N \times N のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と表します。

始め、(1,1) に駒が 1 個置かれています。あなたは以下の操作を何度でも行うことができます。

  • 今駒が置かれているマスと距離がちょうど \sqrt{M} であるマスに駒を移動させる。

ここで、マス (i,j) とマス (k,l) の距離は \sqrt{(i-k)^2+(j-l)^2} とします。

全てのマス (i,j) に対して、以下の問題を解いてください。

  • 駒を (1,1) から (i,j) に移動させることができるかを判定し、できる場合は操作回数の最小値を求めてください。

制約

  • 1 \le N \le 400
  • 1 \le M \le 10^6
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

N 行出力せよ。i 行目には N 個の整数を出力せよ。i 行目の j 個目の出力は、マス (i,j) に駒を移動させることができるのであれば操作回数の最小値を、そうでないのであれば -1 を出力せよ。

入力例 1

3 1

出力例 1

0 1 2
1 2 3
2 3 4

駒は上下左右の 4 個のマスに移動することができます。

例えば (2,2) に移動するには、以下のように 2 回の操作を行えばよいです。

  • 今駒は (1,1) に置かれている。(1,1) と (1,2) の距離はちょうど \sqrt{1} であるため、駒を (1,2) に移動させる。
  • 今駒は (1,2) に置かれている。(1,2) と (2,2) の距離はちょうど \sqrt{1} であるため、駒を (2,2) に移動させる。

入力例 2

10 5

出力例 2

0 3 2 3 2 3 4 5 4 5
3 4 1 2 3 4 3 4 5 6
2 1 4 3 2 3 4 5 4 5
3 2 3 2 3 4 3 4 5 6
2 3 2 3 4 3 4 5 4 5
3 4 3 4 3 4 5 4 5 6
4 3 4 3 4 5 4 5 6 5
5 4 5 4 5 4 5 6 5 6
4 5 4 5 4 5 6 5 6 7
5 6 5 6 5 6 5 6 7 6

Score : 400 points

Problem Statement

There is a grid with N \times N squares. We denote by (i, j) the square at the i-th row from the top and j-th column from the left.

Initially, a piece is placed on (1, 1). You may repeat the following operation any number of times:

  • Let (i, j) be the square the piece is currently on. Move the piece to the square whose distance from (i, j) is exactly \sqrt{M}.

Here, we define the distance between square (i, j) and square (k, l) as \sqrt{(i-k)^2+(j-l)^2}.

For all squares (i, j), determine if the piece can reach (i, j). If it can, find the minimum number of operations required to do so.

Constraints

  • 1 \le N \le 400
  • 1 \le M \le 10^6
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M

Output

Print N lines. The i-th line should contain N integers. If the piece can reach (i, j), the j-th integer in the i-th line should be the minimum number of operations required to do so; otherwise, it should be -1.

Sample Input 1

3 1

Sample Output 1

0 1 2
1 2 3
2 3 4

You can move the piece to four adjacent squares.

For example, we can move the piece to (2,2) with two operations as follows.

  • The piece is now on (1,1). The distance between (1,1) and (1,2) is exactly \sqrt{1}, so move the piece to (1,2).
  • The piece is now on (1,2). The distance between (1,2) and (2,2) is exactly \sqrt{1}, so move the piece to (2,2).

Sample Input 2

10 5

Sample Output 2

0 3 2 3 2 3 4 5 4 5
3 4 1 2 3 4 3 4 5 6
2 1 4 3 2 3 4 5 4 5
3 2 3 2 3 4 3 4 5 6
2 3 2 3 4 3 4 5 4 5
3 4 3 4 3 4 5 4 5 6
4 3 4 3 4 5 4 5 6 5
5 4 5 4 5 4 5 6 5 6
4 5 4 5 4 5 6 5 6 7
5 6 5 6 5 6 5 6 7 6