题解

思路

设真实行号为 $x$，已经经过的时间为 $d$，定义相对行号 $X=(x+d)\bmod n$。初始第 $r$ 行的石头在时刻 $d$ 位于 $r-d$，故此时真实位置 $x+k$ 是否有石头，等价于检查初始矩阵第 $X+k$ 行。

在相对坐标中，向上后 $X$ 不变，向右后 $X$ 增加一，向下后 $X$ 增加二。向上因此只是相对状态的自环，不会帮助抵达新列或绕过石头，可以留到末尾统一补做。

做法

在 $n\times m$ 个状态 $(X,y)$ 上广度优先搜索。由 $(X,y)$：

• 若 $a_{X+1,y}=a_{X+2,y}=0$，可走到 $(X+2,y)$；
• 若 $y+1<m$ 且 $a_{X+1,y+1}=0$，可走到 $(X+1,y+1)$。

行号均对 $n$ 取模。设到达末列状态 $(X,m-1)$ 的距离为 $d$，此时真实行号是 $X-d$。再向上走 $u=(X-d+1)\bmod n$ 步即可到达真实行 $n-1$。答案为所有可达末列状态的 $d+u$ 最小值。

小规模验证程序直接在 $(x,y,d\bmod n)$ 的真实时空状态上广搜；独立满分程序用优先队列 Dijkstra 计算同一相对图，以交叉验证状态变换和边界。

正确性证明

相对坐标的三类转移由 $X=x+d$ 直接代入得到，石头检测位置也恰由石头每秒上移一格得到，故所有保留的右移、下移边与原问题一一对应。向上边保持相对状态不变；把路径中的向上操作移到路径末尾不会改变任何后续相对状态和石头检测，因此不会破坏合法性，也不增加总步数。广搜给出不含向上自环的最短距离，末尾补的 $u$ 是到目标真实行所需的最少非负向上步数。枚举末列的所有相对行即得到全局最优答案。

复杂度

每组时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。