CF358E.Dima and Kicks
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Dima is a good person. In fact, he's great. But all good things come to an end...
Seryozha is going to kick Dima just few times.. For this reason he divides the room into unit squares. Now the room is a rectangle n × m consisting of unit squares.
For the beginning, Seryozha put Dima in a center of some square. Then he started to kick Dima (it is known, that he kicks Dima at least once). Each time when Dima is kicked he flyes up and moves into one of four directions (up, left, right, down). On each move Dima passes k (k > 1) unit of the length in the corresponding direction. Seryozha is really kind, so he kicks Dima in such way that Dima never meets the walls (in other words, Dima never leave the room's space). Seryozha is also dynamic character so Dima never flies above the same segment, connecting a pair of adjacent squares, twice.
Seryozha kicks Dima for a long time, but Dima is not vindictive — Dima writes. Dima marked all squares in which he was staying or above which he was flying. Thanks to kicks, Dima does not remember the k value, so he asks you to find all possible values which matches to the Dima's records.
迪马是个好人,事实上,他非常棒。但所有美好的事物终将结束……
谢尔盖要踢迪马几下……为此,他把房间划分成了单位正方形。现在房间是一个 n×m 的矩形,由单位正方形构成。
一开始,谢尔盖把迪马放在某个正方形的中心。接着他开始踢迪马(已知他至少踢一次)。每次迪马被踢时,他都会腾空而起,并朝四个方向之一(上、左、右、下)移动。每次移动中,迪马在对应方向上行进 k(其中 k>1)个单位长度。谢尔盖非常善良,因此他踢迪马的方式保证迪马永远不会碰到墙壁(换句话说,迪马始终不会离开房间范围)。谢尔盖还是一个充满活力的人,因此迪马绝不会两次飞越连接一对相邻正方形的同一条线段(即每条单位边至多被飞越一次)。
谢尔盖踢了迪马很长时间,但迪马并不记仇——他选择记录下来。迪马标记了所有他曾停留过的正方形,以及他曾飞越其上方的所有正方形。由于踢击的影响,迪马已不记得 k 的值,因此他请你找出所有与迪马记录相符的可能的 k 值。
输入格式
The first line contains n and m (1 ≤ n, m ≤ 103) — size of the room.
Next n lines goes, each contains m numbers a__ij — Dima's notes: a__ij = 1, if Dima was staying in the square (i, j) or was flying above it. Otherwise a__ij = 0.
At least one a__ij equals 1.
第一行包含 n 和 m(1 ≤ n, m ≤ 103)——房间的尺寸。
接下来是 n 行,每行包含 m 个数字 aij —— Dima 的记录:若 Dima 曾停留在格子 (i,j) 上或曾飞越其正上方,则 aij=1;否则 aij=0。
至少存在一个 aij=1。
输出格式
In a single line in accending order print all k (k > 1), which matches the Dima's notes. If there are no such k and Dima invented this story with kicks, print -1.
在一行中按升序输出所有满足 Dima 笔记的 k(k>1)。如果不存在这样的 k(即 Dima 编造了这个踢球的故事),则输出 -1。
输入输出样例
输入#1
5 5 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1
输出#1
2 4
输入#2
7 7 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0
输出#2
2
输入#3
3 3 1 1 1 1 1 1 1 1 1
输出#3
-1
输入#4
4 4 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
输出#4
3
输入#5
5 5 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0
输出#5
-1
输入解题思路,AI测评打分。不知道怎么写?