TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3171
  • 题目
  • P3171逃离迷宫2
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    有一个方格迷宫,我们可以将它看作一个n*m的矩阵,每个方格表示一个房间,方格中有数字0和1,数字0表示该房间是空的,可以顺利通过,数字1表示该房间有怪兽,不能通过。
    一开始何老板位于左上角的方格(坐标[1,1]位置),他要走到右下角的出口(坐标[n,m]位置),每一步何老板可以往上、下、左、右走。
    他想知道最少需要几步就可以走出迷宫?

    输入格式

    第一行,两个整数n和m
    接下来是一个有数字0和1构成的n*m的矩阵,表示迷宫

    输出格式

    一个整数,表示最小步数。若无解,输出-1

    样例输入

    4 5
    0 0 0 0 0
    0 1 1 1 0
    0 1 0 0 0
    0 0 0 1 0

    样例输出

    7

    提示

    1<=n,m<=20