← 返回题目列表

Codeforces · 1933/F

F. 海龟任务:机器人与地震

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

世界是一个由 $$$n$$$ 行和 $$$m$$$ 列组成的网格。行的编号为 $$$0, 1, \ldots, n-1$$$,而列的编号为 $$$0, 1, \ldots, m-1$$$。在这个世界中,列是循环的(即每列中的顶部和底部单元格是相邻的)。第 $$$i$$$ 行和第 $$$j$$$ 列上的单元格 ($$$0 \le i < n, 0 \le j < m$$$) 表示为 $$$(i,j)$$$。

在时间$$$0$$$,单元格$$$(i,j)$$$(其中$$$0 \le i < n, 0 \le j < m$$$)要么包含岩石,要么什么也没有。单元$$$(i,j)$$$的状态可以使用整数$$$a_{i,j}$$$来描述:

- 如果 $$$a_{i,j} = 1$$$,则 $$$(i,j)$$$ 处有一块岩石。
- 如果 $$$a_{i,j} = 0$$$,则 $$$(i,j)$$$ 处没有任何内容。

由于地震余震,这些柱子跟随构造板块运动:每根柱子以每单位时间 $$$1$$$ 单元格的速度循环向上移动。形式上,对于某些$$$0 \le i < n, 0 \le j < m$$$,如果$$$(i,j)$$$此时包含一块岩石,它将从$$$(i, j)$$$移动到$$$(i - 1, j)$$$(或者如果$$$i=0$$$则移动到$$$(n - 1, j)$$$)。

名为 RT 的机器人最初位于 $$$(0,0)$$$。它必须前往$$$(n-1,m-1)$$$执行地震救援行动(到最右下角的单元格)。地震不会改变机器人的位置,只会改变世界上岩石的位置。

设RT的当前位置为$$$(x,y)$$$ ($$$0 \le x < n, 0 \le y < m$$$),它可以执行以下操作:

- 循环向上移动一个单元格,即使用 $$$1$$$ 时间单位从 $$$(x,y)$$$ 到 $$$((x+n-1) \bmod n, y)$$$。
- 循环向下移动一个单元格,即使用 $$$1$$$ 时间单位从 $$$(x,y)$$$ 到 $$$((x+1) \bmod n, y)$$$。
- 向右移动一个单元格,即使用 $$$1$$$ 时间单位从 $$$(x,y)$$$ 到 $$$(x, y+1)$$$。 (仅当 $$$y < m-1$$$ 时,RT 才可以执行此操作。)

请注意,RT 不能使用操作向左移动,也不能停留在某个位置。

不幸的是,RT 与岩石碰撞时会爆炸。因此,当 RT 位于 $$$(x,y)$$$ 且 $$$((x+1) \bmod n, y)$$$ 或 $$$((x+2) \bmod n, y)$$$ 处有一块岩石时,RT 无法向下移动,否则会被岩石击中。

同样,如果 $$$y+1 < m$$$ 并且 $$$((x+1) \bmod n, y+1)$$$ 处有一块岩石,RT 无法向右移动,否则会被岩石击中。

不过,值得注意的是,如果$$$(x \bmod n, y+1)$$$和$$$((x+1) \bmod n, y)$$$处有岩石,RT仍然可以安全地向右移动。

求 RT 在不与任何岩石碰撞的情况下达到 $$$(n-1,m-1)$$$ 所需的最短时间。如果不可能,则输出$$$-1$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

在每个测试用例中,第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$3 \le n, m \le 10^3$$$) — 行星边界的大小。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个整数。第 $$$(i+1)$$$ 行上的第 $$$(j+1)$$$ 整数 ($$$0 \le i < n, 0 \le j < m$$$) 为 $$$a_{i,j}$$$ ($$$0 \le a_{i,j} \le 1$$$),表示此时 $$$(i,j)$$$ 处是否有岩石$$$0$$$。

此外,保证 $$$a_{0,0} = 0$$$,并且 $$$a_{i, m-1} = 0$$$ 对于 $$$0 \le i < n$$$。换句话说,RT 的初始位置以及$$$m-1$$$ 列都没有岩石。

所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例:

- 如果可以在不碰撞任何岩石的情况下到达目的地,则输出一个整数 - RT 到达 $$$(n-1,m-1)$$$ 所需的最短时间。
- 否则,输出$$$-1$$$。

示例

输入 #1

6
4 5
0 1 0 0 0
0 0 1 0 0
1 0 1 1 0
0 0 0 0 0
3 3
0 0 0
1 0 0
0 0 0
5 3
0 0 0
0 0 0
1 0 0
0 0 0
1 0 0
3 7
0 0 1 0 0 1 0
1 0 1 0 1 0 0
0 1 0 0 0 0 0
3 4
0 1 0 0
1 0 0 0
0 1 1 0
5 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0

输出 #1

7
3
3
8
-1
12

输入 #2

6
3 3
0 0 0
0 0 0
0 0 0
4 3
0 1 0
1 0 0
0 1 0
1 0 0
4 3
0 1 0
0 1 0
0 1 0
0 1 0
3 3
0 0 0
1 1 0
0 0 0
3 3
0 1 0
0 0 0
0 1 0
5 5
0 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 1 0 0

输出 #2

3
3
-1
-1
3
8

注意

示例中第一个测试用例的直观解释: