题目描述

给定一个 n × m 的二维数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走，1 表示不可通过。

最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。若无法走到终点，则输出-1。

输入描述

第一行一个正整数 T ( 1 <= T <= 10³ ) 表示数据组数。

每组测试数据描述如下：

第一行两个正整数 n , m ( 1 <= n × m <= 10⁶ ), n , m 表示迷宫的长和宽。

接下来 n 行，每行有 m 个字符 s_i ( s_i 当且仅当只会是 0 和 1 )

确保起点 ( 1 , 1 ) 处一定为0 , n × m 不超过 10⁶ 。

输出描述

若能走到迷宫终点，输出移动到终点的最少步数；若走不到终点，则输出 -1。

样例

1
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

8

解释

用x表示走过的道路，正确的行走路径为：

x 1 0 0 0
x 1 0 1 0
x x x x x
0 1 1 1 x
0 0 0 1 x

提示

每一步的可选择方向：

x 1 0 0 0    x 1 0 0 0    x 1 0 0 0    x 1 0 0 0
0 1 0 1 0    x 1 0 1 0    x 1 0 1 0    x 1 0 1 0
0 0 0 0 0 -> 0 0 0 0 0 -> x 0 0 0 0 -> x x 0 0 0 ->
0 1 1 1 0    0 1 1 1 0    0 1 1 1 0    x 1 1 1 0
0 0 0 1 0    0 0 0 1 0    0 0 0 1 0    0 0 0 1 0

x 1 0 0 0    x 1 0 0 0    x 1 0 0 0    x 1 0 0 0    x 1 0 0 x
x 1 0 1 0    x 1 0 1 0    x 1 0 1 0    x 1 0 1 x    x 1 0 1 x
x x x 0 0 -> x x x x 0 -> x x x x x -> x x x x x -> x x x x x
x 1 1 1 0    x 1 1 1 0    x 1 1 1 0    x 1 1 1 x    x 1 1 1 x
x 0 0 1 0    x x 0 1 0    x x x 1 0    x x x 1 0    x x x 1 x

限制范围

每个测试样例限制为1s, 248Mb。