[ABC272D] Root M Leaper

robinyqc · 2022-10-28 19:28:51 · 题解

洛谷链接 原题链接

题目描述

有一个大小为 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) 。
2. 现在棋子在 (1,2) 了。(1,2) 到 (2,2)的距离也刚好是 \sqrt 1 ，所以我们就把它移到了 (2,2) 。