CF1933F.Turtle Mission: Robot and the Earthquake

The world is a grid with $n$ rows and $m$ columns. The rows are numbered $0, 1, \ldots, n-1$, while the columns are numbered $0, 1, \ldots, m-1$. In this world, the columns are cyclic (i.e. the top and the bottom cells in each column are adjacent). The cell on the $i$-th row and the $j$-th column ($0 \le i \lt n, 0 \le j \lt m$) is denoted as $(i,j)$.

At time $0$, the cell $(i,j)$ (where $0 \le i \lt n, 0 \le j \lt m$) contains either a rock or nothing. The state of cell $(i,j)$ can be described using the integer $a_{i,j}$:

• If $a_{i,j} = 1$, there is a rock at $(i,j)$.
• If $a_{i,j} = 0$, there is nothing at $(i,j)$.

As a result of aftershocks from the earthquake, the columns follow tectonic plate movements: each column moves cyclically upwards at a velocity of $1$ cell per unit of time. Formally, for some $0 \le i \lt n, 0 \le j \lt m$, if $(i,j)$ contains a rock at the moment, it will move from $(i, j)$ to $(i - 1, j)$ (or to $(n - 1, j)$ if $i=0$).

The robot called RT is initially positioned at $(0,0)$. It has to go to $(n-1,m-1)$ to carry out an earthquake rescue operation (to the bottom rightmost cell). The earthquake doesn't change the position of the robot, they only change the position of rocks in the world.

Let RT's current position be $(x,y)$ ($0 \le x \lt n, 0 \le y \lt m$), it can perform the following operations:

• Go one cell cyclically upwards, i.e. from $(x,y)$ to $((x+n-1) \bmod n, y)$ using $1$ unit of time.
• Go one cell cyclically downwards, i.e. $(x,y)$ to $((x+1) \bmod n, y)$ using $1$ unit of time.
• Go one cell to the right, i.e. $(x,y)$ to $(x, y+1)$ using $1$ unit of time. (RT may perform this operation only if $y \lt m-1$.)

Note that RT cannot go left using the operations nor can he stay at a position.

Unfortunately, RT will explode upon colliding with a rock. As such, when RT is at $(x,y)$ and there is a rock at $((x+1) \bmod n, y)$ or $((x+2) \bmod n, y)$, RT cannot move down or it will be hit by the rock.

Similarly, if $y+1 \lt m$ and there is a rock at $((x+1) \bmod n, y+1)$, RT cannot move right or it will be hit by the rock.

However, it is worth noting that if there is a rock at $(x \bmod n, y+1)$ and $((x+1) \bmod n, y)$, RT can still move right safely.

Find the minimum amount of time RT needs to reach $(n-1,m-1)$ without colliding with any rocks. If it is impossible to do so, output $-1$.

世界是一个 $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$），其可执行以下操作：

• 循环向上移动一格：即从 $(x,y)$ 移至 $((x+n-1) \bmod n, y)$，耗时 $1$ 单位；
• 循环向下移动一格：即从 $(x,y)$ 移至 $((x+1) \bmod n, y)$，耗时 $1$ 单位；
• 向右移动一格：即从 $(x,y)$ 移至 $(x, y+1)$，耗时 $1$ 单位。（RT 仅当 $y < m-1$ 时方可执行此操作。）

注意：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$。

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

In each test case, the first line contains two integers $n$, $m$ ($3 \le n, m \le 10^3$) — the size of the planet's boundaries.

Each of the next $n$ lines contains $m$ integers. The $(j+1)$-th integer on the $(i+1)$-th line ($0 \le i \lt n, 0 \le j \lt m$) is $a_{i,j}$ ($0 \le a_{i,j} \le 1$), which denotes whether or not there is a rock at $(i,j)$ at time $0$.

Additionally, it is guaranteed that $a_{0,0} = 0$, and $a_{i, m-1} = 0$ for $0 \le i \lt n$. In other words, there is no rock at RT's initial position as well as column $m-1$.

The sum of $n \cdot m$ over all test cases does not exceed $10^6$.

输入的第一行包含一个整数 $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$），表示在时刻 $0$ 位置 $(i,j)$ 处是否存在一块岩石。

此外，保证 $a_{0,0} = 0$，且对所有 $0 \le i < n$ 均有 $a_{i, m-1} = 0$。换言之，RT 的初始位置以及第 $m-1$ 列均没有岩石。

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

For each test case:

• If the destination can be reached without colliding with any rocks, output a single integer — the minimum amount of time RT needs to reach $(n-1,m-1)$.
• Otherwise, output $-1$.

对于每个测试用例：

• 如果可以在不与任何岩石碰撞的情况下到达目标位置，则输出一个整数——RT 到达 $(n-1,m-1)$ 所需的最少时间；
• 否则，输出 $-1$。

Visual explanation of the first test case in the example:

示例中第一个测试用例的可视化解释：