102723: [AtCoder]ABC272 D - Root M Leaper
Description
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
Input
题意翻译
### 题目描述 有一个大小为 $N\times N$ 的方格图（网格）。在本题中，我们所说的方格 $(i,j)$ 指网格从上往下数第 $i$ 行，从左往右数第 $j$ 列。 最开始，有一个棋子位于方格 $(1,1)$ 。现在你可以进行下面这个操作若干次： + 当前棋子位于 $(i,j)$ ，那么移动它到一个距离它刚好 $\sqrt{M}$ 的点（不超出网格）。 本题中的“**距离**”，指欧几里得距离。即方格 $(i,j)$ 与 $(k,l)$ 的距离是 $\sqrt{(i-k)^2+(j-l)^2}$ 。 现在对于整个网格，请你确定棋子能否到达方格 $(i,j)$ 。如果可以，输出到达它的最少操作次数；如果不行，输出 ```-1``` 。 ### 输入格式 输入两个正整数 $N$ ， $M$ 。 >$N\ M$ ### 输出格式 输出共 $N$ 行。 第 $i$ 行包含 $N$ 个整数，中间以一个空格隔开。如果棋子可以到达方格 $(i,j)$ ，第 $i$ 行第 $j$ 列应输出到达它的最少操作次数；如果不行，输出 ```-1``` 。 ### 说明/提示 #### 数据范围 - $ 1\ \le\ N\ \le\ 400 $ - $ 1\ \le\ M\ \le\ 10^6 $ - 输入全为整数 #### 样例说明 对于**样例1**，你可以把棋子通过一定次数的操作挪到这个方格图的任意位置。 比如说，我们可以通过如下操作把棋子移到 $(2,2)$ ： 1. 开始棋子在 $(1,1)$ 。 $(1,1)$ 到 $(1,2)$ 的距离刚好是 $\sqrt 1$ ，所以我们把它移到 $(1,2)$ 。 1. 现在棋子在 $(1,2)$ 了。$(1,2)$ 到 $(2,2)$的距离也刚好是 $\sqrt 1$ ，所以我们就把它移到了 $(2,2)$ 。Output
问题描述
有一个包含 $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)$。如果可以，找出所需的最小操作次数。
限制条件
- $1 \le N \le 400$
- $1 \le M \le 10^6$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出，格式如下：
$N$ $M$
输出
打印 $N$ 行。第 $i$ 行的第 $j$ 个整数表示，如果棋子可以到达 $(i, j)$，则输出所需的最小操作次数；否则，输出 $-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