题意简述

• 有一个 $n$ 行 $m$ 列的网格，列循环（第 $0$ 行和第 $n-1$ 行相邻）。
• 初始时某些格子有岩石（$a_{i,j}=1$）。
• 岩石随时间循环向上移动：每单位时间行号减 $1$（$0$ 行会到 $n-1$ 行）。
• 机器人从 $(0,0)$ 出发，要到达 $(n-1,m-1)$。
• 机器人可以：
  1. 向上（循环） — 时间 $+1$
  2. 向下（循环） — 时间 $+1$
  3. 向右（仅当 $y<m-1$） — 时间 $+1$
• 机器人不能撞岩石：
  • 向下移动前，要检查 $(x+1)\bmod n$ 和 $(x+2)\bmod n$ 当前是否有岩石。
  • 向右移动前，要检查 $(x+1)\bmod n$ 在下一列当前是否有岩石。
• 求最短时间，不能则 $-1$。

---

核心观察 — 相对运动

这是本题最难也最巧妙的一步。

关键：岩石每单位时间向上 $1$ 格。
如果我们站在机器人视角看岩石，相当于机器人每过 $1$ 单位时间，岩石向下移动 $1$ 格。

因此，我们可以把机器人的移动在相对坐标系下重写。

设相对运动后的坐标仍为 $(x,y)$，含义与原来相同，但时间变化时岩石位置不变。

原移动 → 相对移动

1. 机器人原向上（$x \to (x-1)\bmod n$，时间 $+1$）
   岩石也向上 $1$ → 相对静止
   → 相对坐标不变，时间 $+1$ → 实际等价于等待（浪费 1 时间，位置不变）

2. 机器人原向下（$x \to (x+1)\bmod n$，时间 $+1$）
   岩石向上 $1$，相对位移 $+2$
   → 相对移动：$(x,y) \to ((x+2)\bmod n, y)$

3. 机器人原向右（$y \to y+1$，时间 $+1$）
   岩石向上 $1$，相对位移 $+1$
   → 相对移动：$(x,y) \to ((x+1)\bmod n, y+1)$

因此，在新的相对运动下：

• 向上移动 → 原地不动（浪费 1 时间，一般不优，可以忽略）
• 向下移动 → 行 $+2$
• 向右移动 → 行 $+1$，列 $+1$

且岩石在相对坐标系中固定不动。

---

新问题模型

我们有一个静态的岩石网格 $a_{i,j}$，机器人从 $(0,0)$ 出发：

• 每步时间 $+1$
• 操作：
  1. 向下：$(x,y) \to ((x+2)\bmod n, y)$
  2. 向右：$(x,y) \to ((x+1)\bmod n, y+1)$
• 不能走进有岩石的格子（$a_{x,y}=1$）
• 不能走进会导致撞岩石的情况：
  • 向下前检查 $a_{(x+1)\bmod n, y}$ 和 $a_{(x+2)\bmod n, y}$（因为从 $x$ 到 $x+2$，中间会经过 $x+1$ 和 $x+2$？等一下要小心）

仔细分析新模型下的碰撞条件：

原条件：

• 原向下前检查 $(x+1)\bmod n$ 和 $(x+2)\bmod n$ 有岩石 → 不能下。 在新模型中，向下相当于原向下 + 岩石向上，所以检查的是当前相对坐标的下一行和再下一行是否有岩石（因为那是实际位置在那一时刻会撞到的）。

  实际上，原题的条件在新模型中可以直接翻译为：

  • 要执行“新向下” $(x,y) \to (x+2, y)$，必须保证 $a_{x+1, y} = 0$ 且 $a_{x+2, y} = 0$。

• 原向右前检查 $(x+1)\bmod n, y+1$ 有岩石 → 不能右。 在新模型中，向右后 $(x+1, y+1)$，而岩石固定，所以检查 $a_{x+1, y+1} = 0$ 即可。

向上操作在新模型中无位移，只会浪费时间，所以最优解中不会使用（除非为了等某个周期，但题目问最小时间，不会故意等）。

---

算法步骤（对标程的解释）

标程中：

• 将列从 $1$ 到 $m$ 编号（$j=1$ 为第一列）。
• $dp[x][j]$ 表示到达相对坐标 $(x, j)$ 的最小时间。
• 初始 $dp[0][1] = 0$。

第一轮转移：来自左边的列

dp[j][i] = min(dp[j][i], dp[(j - 1 + n) % n][i - 1] + 1);

这对应 向右移动 操作：

• 从 $( (j-1)\bmod n, i-1)$ 向右移动到 $(j, i)$
• 时间 $+1$

但这里没有检查 $a[j][i]$ 是否为岩石（前面有 if(a[j][i]) continue;），因为不能走入有岩石的格子。

并且注意，新模型中向右移动是 $(x,y) \to (x+1, y+1)$，所以来源行是 $j-1$，目标行 $j$。对，这里 j 是行号，i 是列号。

第二轮转移：同一列内向下移动

for (int j = 0; j < 3 * n; j++) {
    if (a[j % n][i] || a[(j - 1 + n) % n][i]) continue;
    dp[j % n][i] = min(dp[j % n][i], dp[(j - 2 + n) % n][i] + 1);
}

这对应 向下移动 操作：

• 从行 $(j-2)\bmod n$ 在同一列向下两次（模 $n$）到行 $j \bmod n$。
• 但必须保证中间行 $j-1$ 和 $j$ 没有岩石（因为新模型下从 $x$ 到 $x+2$ 需要经过 $x+1$ 和 $x+2$，即检查 $a[x+1]$ 和 $a[x+2]$，这里循环写法是检查 a[(j-1)%n] 和 a[j%n]）。

为什么要循环 $3n$ 次？

• 因为向下移动是模 $n$ 的，从 $0$ 开始向下走，可能绕多圈，但最优解中不会绕超过 $2n$ 步（因为绕整圈回到原行浪费时间）。这里用 $3n$ 确保覆盖所有可能的转移。

---

最后从最后一列到终点

标程中 $m$ 列是最后一列（题目保证无岩石），但我们的相对坐标系里，最后一列是 $m$ 吗？

注意：原题 $m$ 列，$j$ 从 $0$ 到 $m-1$，这里标程将列右移 1，$i=1$ 对应原第一列，$i=m$ 对应原最后一列。

但机器人要去 $(n-1, m-1)$，原坐标。在相对模型中，最后一列是 $m$，行需要是某个 $x$。

我们如何从最后一列到终点？

在原问题中，到达 $(n-1, m-1)$ 后，游戏结束。但我们的相对模型只走到最后一列，还需要考虑最后一列的行位置如何调整到目标行。

因为岩石还在运动，我们可以在最后一列等待（原操作中的向上/向下，在相对模型中会改变行），直到行变成 $n-1$。

具体：

• 假设在最后一列 $m$ 的行 $i$，已用时间 $dp[i][m]$。
• 当前岩石已经向上移动了 $dp[i][m]$ 次（因为时间是 $t$，岩石向上 $t$）。
• 我们看终点 $(n-1, m-1)$ 在当前实际世界中的位置：
  实际行 = $(n-1 + t) \bmod n$？不，要小心。

更简单的做法（标程做法）：

• 在相对模型中，最后一列的行 $i$ 对应原坐标的 $(i, m-1)$。
• 原目标行是 $n-1$，差为 $d = (n-1 - i) \bmod n$。
• 由于我们在最后一列可以原地上下（相对模型中的上下就是原上下，会花费时间），每向上/向下一步时间 $+1$，行变化 $\pm 1$。
• 所以最少等待时间 = $\min(d, n-d)$。

但标程写的是：

int npos = ((n - 1) + dp[i][m]) % n;
if (npos < i) npos += n;
int cur = dp[i][m] + min(npos - i, n - (npos - i));

这里 $npos$ 是在 $dp[i][m]$ 时间后，原目标行 $(n-1)$ 因为岩石向上运动而偏移到的位置。然后计算从当前行 $i$ 到 $npos$ 的模 $n$ 最短距离。这是正确的。

---

复杂度

• 每列：$O(n)$ 来自左边列，$O(3n)$ 来自同列向下
• 总列 $m$：$O(nm)$
• 总 $n\cdot m \le 10^6$，可过。

---

总结

这道题的精华在于：

1. 相对运动变换：把移动的岩石变成静态，同时改变机器人的移动规则。
2. 向上操作在新模型中无用，简化问题。
3. BFS/DP 按列递推，最后一列再处理行偏移。
4. 碰撞条件在相对模型下 转化为检查固定岩石位置。

这样，原题复杂的动态障碍物问题，转化成了一个带特殊移动规则的静态网格最短路问题。

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int t;
    cin >> t;
    while (t--){
        int n, m;
    	cin >> n >> m;
    	bool a[n][m + 1];
    	for (int i = 0; i < n; i++) {
    		for (int j = 1; j <= m; j++) {
    			cin >> a[i][j];
    		}
    	}
    	int dp[n][m + 1];
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j <= m; j++) {
    			dp[i][j] = INT_MAX;
    		}
    	}
    	dp[0][1] = 0;
    	for (int i = 1; i <= m; i++) {
    		for (int j = 0; j < n; j++) {
    			if (a[j][i]){
    			    continue;
    			}
    			dp[j][i] = min(dp[j][i], dp[(j - 1 + n) % n][i - 1] + 1); 
    		}
    		for (int j = 0; j < 3 * n; j++) {
    			if (a[j % n][i] || a[(j - 1 + n) % n][i]){
    			    continue;
    			}
    			dp[j % n][i] = min(dp[j % n][i], dp[(j - 2 + n) % n][i] + 1);
    		}
    	}
    	int ans = INT_MAX;
    	for (int i = 0; i < n; i++) {
    		if (dp[i][m] == INT_MAX){
    		    continue;
    		}
    		int npos = ((n - 1) + dp[i][m]) % n;
    		if (npos < i) npos += n;
    		int cur = dp[i][m] + min(npos - i, n - (npos - i));
    		ans = min(ans, cur);
    	}
    	if(ans == INT_MAX){
    	    cout << -1 << endl;
    	}else{
    	    cout << ans << endl;
    	}
    }
}