5614 - 提高:迷宫问题(传送)

简单描述:在一个n行m列的表格里,你在左上角1,1位置,你准备到右下角,即可n行m列的位置,在这个表格里,你只能向下或向右走;另外,你可以进行若干次传送,每次可以花费1的步数,前往和当前房间不互素的任意一个房间。 现在,希望你求出从左上角走到右下角的最小步数

输入

第一行输入两个正整数n,m,代表迷宫的行数和列数。 接下来的n行,每行输入m个正整数aij ,用来表示每个房间的数字。1≤n,m≤500 , 1≤aij ≤10^5

输出

一个整数,代表左上角走到右下角的最小步数。

样例

输入

3 3
1 2 3
2 3 3
3 4 5

输出

3

提示

第一步,向右走一步,当前格子为2。 第二步,传送到第三行第二列的4。 第三步,向右走一步。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题