/ Vijos / 题库 /

迷宫

迷宫

题目描述

给定一个NM列的迷宫,每次只能向上、下、左、右四个方向走一步,问从左上角(0,0)走至右下角(N-1,M-1)所需的最小步数。

输入格式

第一行为2个正整数N,M,用一个空格隔开
接下来N行,每行M个数,1表示可通过,0表示不可通过
(起始点和终止点也可能为0

输出格式

一行,一个整数,表示最小步数,若不能到达,输出-1

输入样例

3 3
1 1 1
1 0 1
0 0 1

输出样例

4

数据范围

20%的数据,NM1
30%的数据,全部节点均为1
70%的数据,1<=N<=M<=5
100%的数据,1<=N<=M<=1000

限制

每个测试点时间1秒,内存128MiB

信息

ID
1007
难度
9
分类
(无)
标签
(无)
递交数
7
已通过
3
通过率
43%
上传者

相关