P13096 [FJCPC 2025] 难以控制的滑板火箭

在一个 $n\times m$ 的 `01` 网格中，其中第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$，若 $a_{i,j}=1$ 则表示这个位置为空地，反之若 $a_{i,j}=0$ 则表示这个位置上有障碍物。 现在小猫从 $(1,1)$ 出发，想要去 $(n,m)$。 若小猫当前在 $(x,y)$ 则**一次移动**后可以到 $(x-1,y)$、$(x+1,y)$、$(x,y-1)$、$(x,y+1)$、$(x-1,y-1)$、$(x+1,y-1)$、$(x-1,y+1)$、$(x+1,y+1)$ 的位置上，注意不能移动到地图外，也不能走到障碍物上。即任意时候 $1\leq x\leq n,1\leq y\leq m,a_{x,y}=1$。 因为小猫使用了难以控制的滑板火箭，每一分钟都会移动 $[l,r]$ 次。 现在需要你求出小猫最少需要几分钟才能成功抵达终点（**必须要某一分钟的移动全部结束后小猫的位置在 $(n,m)$ 才算成功抵达**），如果无论经过多久都不能成功抵达请输出 `-1`。

第一行一个整数 $t$（$1\leq t\leq 1000$），表示测试数据组数。 接下来对于每一组测试数据，第一行两个整数 $n,m$（$2\leq n,m\leq 1000$），表示 `01` 网格的大小。 接下来一行包含两个整数 $l,r$（$1\leq l\leq r\leq 10^9$），表示在一分钟内移动次数的限制范围。 接下来 $n$ 行，每行 $m$ 个字符，表示网格的元素 $a_{i,j}$，字符仅会出现 `0` 或 `1`，且 $a_{1,1}$ 与 $a_{n,m}$ 一定为 $1$。 保证所有测试数据的 $n\times m$ 的和不超过 $10^6$。

对于每一组测试数据输出一行，如果小猫能在有限时间内抵达 $(n,m)$，那么输出最少需要的分钟数，否则输出 `-1`。

对于第一组样例： 在第一分钟 $(1,1)\rightarrow (2,2)\rightarrow (3,3)\rightarrow (3,4)$； 在第二分钟 $(3,4)\rightarrow (4,5)\rightarrow (5,5)$。