Score : $400$ points

问题描述

存在一个 $N \times N$ 的网格。我们用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。

初始时，棋子位于 $(1, 1)$。你可以任意次数地重复以下操作：

• 让 $(i, j)$ 表示棋子当前所在的格子，将棋子移动到距离 $(i, j)$ 等于 $\sqrt{M}$ 的格子上。

这里，我们定义格子 $(i, j)$ 和格子 $(k, l)$ 之间的距离为 $\sqrt{(i-k)^2+(j-l)^2}$。

对于所有格子 $(i, j)$，确定棋子是否能够到达该格子。如果可以，找出完成这一操作所需的最少步骤数。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:27:48