Root M Leaper

题目描述

有一个由 $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)$。如果可以，找出所需的最小操作次数。

输入格式

输入按以下格式由标准输入提供： $N$ $M$

输出格式

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

3 1

0 1 2
1 2 3
2 3 4

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

提示

$1 \le N \le 400$ $1 \le M \le 10^6$ 输入中的所有数值均为整数。你可以将棋子移动到四个相邻的格子。 例如，我们可以通过如下两步将棋子移动到 $(2,2)$。

棋子现在位于 $(1,1)$。$(1,1)$ 与 $(1,2)$ 之间的距离恰好为 $\sqrt{1}$，所以将棋子移动到 $(1,2)$。 棋子现在位于 $(1,2)$。$(1,2)$ 与 $(2,2)$ 之间的距离恰好为 $\sqrt{1}$，所以将棋子移动到 $(2,2)$。

标签: AtCoder|abc272D

来源

AtCoder|abc272D