#P3006. [五级] 密室逃脱

[五级] 密室逃脱

题目描述

小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。

密室是 mmnn 列的格子矩阵,小Y从左上角 (1,1)(1,1) 进入密室,密室中有三种格子:

  1. 墙,以数字 00 标记;
  2. 路,以数字 11 标记;

隐藏线索处,以数字(>1> 1)标记, 代表该线索的难度。

小Y需要按照难度递增的顺序解开各个线索,逃脱密室。

输入格式

第一行是一个整数 TT1T31 \le T \le 3),表示输入包含 TT 组数据,分别是不同的游戏中小Y所处的密室。

对于每组数据,第一行包括两个整数:mm1m1001 \le m \le 100)、nn1n1001 \le n \le 100)。

接下来 mm 行,每行有 nn 个数字,第 ii 行的第 jj 个数字表示密室中第 ii 行第 jj 列的格子的类型。

题目保证进入密室处 (1,1)(1,1) 不是墙壁,线索的难度都不相同。

输出格式

对于每组数据,你需要输出一个整数,表示小Y在这个密室中至少要移动多少次才能成功通关。

如果小Y不可能解开所有线索,输出 -1

样例

2
3 3
1 3 2
1 0 4
10 6 5
3 3
1 3 2
0 0 0
10 6 5
8
-1