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

    ID: 12784 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>2025福建广度优先搜索 BFSXCPC

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

题目描述

在一个 n×mn\times m01 网格中,其中第 ii 行第 jj 列的元素为 ai,ja_{i,j},若 ai,j=1a_{i,j}=1 则表示这个位置为空地,反之若 ai,j=0a_{i,j}=0 则表示这个位置上有障碍物。

现在小猫从 (1,1)(1,1) 出发,想要去 (n,m)(n,m)

若小猫当前在 (x,y)(x,y)一次移动后可以到 (x1,y)(x-1,y)(x+1,y)(x+1,y)(x,y1)(x,y-1)(x,y+1)(x,y+1)(x1,y1)(x-1,y-1)(x+1,y1)(x+1,y-1)(x1,y+1)(x-1,y+1)(x+1,y+1)(x+1,y+1) 的位置上,注意不能移动到地图外,也不能走到障碍物上。即任意时候 1xn,1ym,ax,y=11\leq x\leq n,1\leq y\leq m,a_{x,y}=1

因为小猫使用了难以控制的滑板火箭,每一分钟都会移动 [l,r][l,r] 次。

现在需要你求出小猫最少需要几分钟才能成功抵达终点(必须要某一分钟的移动全部结束后小猫的位置在 (n,m)(n,m) 才算成功抵达),如果无论经过多久都不能成功抵达请输出 -1

输入格式

第一行一个整数 tt1t10001\leq t\leq 1000),表示测试数据组数。

接下来对于每一组测试数据,第一行两个整数 n,mn,m2n,m10002\leq n,m\leq 1000),表示 01 网格的大小。

接下来一行包含两个整数 l,rl,r1lr1091\leq l\leq r\leq 10^9),表示在一分钟内移动次数的限制范围。

接下来 nn 行,每行 mm 个字符,表示网格的元素 ai,ja_{i,j},字符仅会出现 01,且 a1,1a_{1,1}an,ma_{n,m} 一定为 11

保证所有测试数据的 n×mn\times m 的和不超过 10610^6

输出格式

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

3
5 5
2 3
10000
01000
00110
11001
11111
7 8
3 3
10101000
01010100
10000100
01000010
00100100
00011010
00000001
7 8
4 4
10101000
01010100
10000100
01000010
00100100
00011010
00000001
2
3
3

提示

对于第一组样例:

在第一分钟 $(1,1)\rightarrow (2,2)\rightarrow (3,3)\rightarrow (3,4)$;

在第二分钟 (3,4)(4,5)(5,5)(3,4)\rightarrow (4,5)\rightarrow (5,5)