当前没有测试数据。

D - 根 M 跳板

得分 : $400$ 分

问题描述

有一张 $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)$，判断棋子是否可以到达 $(i, j)$。如果可以，求出达到 $(i, j)$ 所需的最少操作次数。

约束条件

• $1 \le N \le 400$
• $1 \le M \le 10^6$
• 输入中的所有值都是整数。

输入

从标准输入读入数据，输入格式如下：

$N$ $M$

输出

输出 $N$ 行。第 $i$ 行应包含 $N$ 个整数。如果棋子可以达到 $(i, j)$，则第 $i$ 行第 $j$ 列的整数应是到达 $(i, j)$ 所需的最少操作次数；否则，应为 $-1$。

3 1

0 1 2
1 2 3
2 3 4

你可以将棋子移动到四个相邻的方格。

例如，你可以通过以下方式，将棋子移动两次到 $(2,2)$。

• 棋子当前位于 $(1,1)$。方格 $(1,1)$ 到 $(1,2)$ 的距离恰好为 $\sqrt{1}$，因此将棋子移动到 $(1,2)$。
• 棋子当前位于 $(1,2)$。方格 $(1,2)$ 到 $(2,2)$ 的距离恰好为 $\sqrt{1}$，因此将棋子移动到 $(2,2)$。

10 5

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