2267 - 密室逃脱

题目描述

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

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

  1. 墙,以数字 0 标记;

  2. 路,以数字 1 标记;

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

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

输入

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

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

接下来 m 行,每行有 n 个数字,第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。

题目保证进入密室处 (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
说明

样例解释

由于需要按难度顺序解开线索,在第一组数据中,小 Y 第一次移动到 3 时不能解密,在完成 2 之后需要回到 3。最后小 Y 解开 10 时,她成功通关。

来源

电子学会五级

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题