← 返回题目列表

AtCoder · abc272_d

G. 根 M 跳跃者

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个网格 N \times N 方块。 我们表示为 (i, j) 广场 i从顶部开始的第行和 j左起第 列。

最初,一块被放置在 (1, 1)。 您可以多次重复以下操作:

  • 让 (i, j) 是棋子当前所在的方块。 将棋子移动到距离 (i, j) 正是 \sqrt{M}.

这里,我们定义方块之间的距离 (i, j) 和正方形 (k, l) as \sqrt{(i-k)^2+(j-l)^2}.

对于所有方格 (i, j),判断该棋子是否可以到达 (i, j)。 如果可以,请找出执行此操作所需的最少操作数。

约束

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

输入

输入由标准输入按以下格式给出:

N M

输出

打印 N 行。 的 i- 第行应包含 N 整数。 如果这块能达到 (i, j), j- 第一个整数 i-th 行应该是执行此操作所需的最少操作数;否则,应该是 -1.


示例输入 1

3 1

示例输出 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).

示例输入 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