#P13096. [FJCPC 2025] 难以控制的滑板火箭
[FJCPC 2025] 难以控制的滑板火箭
题目描述
在一个 的 01
网格中,其中第 行第 列的元素为 ,若 则表示这个位置为空地,反之若 则表示这个位置上有障碍物。
现在小猫从 出发,想要去 。
若小猫当前在 则一次移动后可以到 、、、、、、、 的位置上,注意不能移动到地图外,也不能走到障碍物上。即任意时候 。
因为小猫使用了难以控制的滑板火箭,每一分钟都会移动 次。
现在需要你求出小猫最少需要几分钟才能成功抵达终点(必须要某一分钟的移动全部结束后小猫的位置在 才算成功抵达),如果无论经过多久都不能成功抵达请输出 -1
。
输入格式
第一行一个整数 (),表示测试数据组数。
接下来对于每一组测试数据,第一行两个整数 (),表示 01
网格的大小。
接下来一行包含两个整数 (),表示在一分钟内移动次数的限制范围。
接下来 行,每行 个字符,表示网格的元素 ,字符仅会出现 0
或 1
,且 与 一定为 。
保证所有测试数据的 的和不超过 。
输出格式
对于每一组测试数据输出一行,如果小猫能在有限时间内抵达 ,那么输出最少需要的分钟数,否则输出 -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)$;
在第二分钟 。