490. 走迷宫
时间限制：1000 MS 内存限制：128 MB
题目描述
# 走迷宫 ## 题目描述 给定一个 $n \times m$ 的二维整数数组，表示一个迷宫。数组中只包含 $0$ 或 $1$，其中 $0$ 表示可以通行的格子，$1$ 表示不可通过的墙壁。 一个人最初位于迷宫的左上角 $(1,1)$。每次移动时，他可以向上、下、左、右中的任意一个方向移动一格，但不能越出迷宫边界，也不能进入墙壁所在的格子。 请你求出从左上角 $(1,1)$ 到右下角 $(n,m)$ 的最少移动次数。 数据保证起点 $(1,1)$ 和终点 $(n,m)$ 均可通行，且至少存在一条从起点到终点的通路。如果起点与终点是同一个格子，则最少移动次数为 $0$。 ## 输入格式 从文件 `maze.in` 读入数据。 第一行包含两个整数 $n$ 和 $m$，分别表示迷宫的行数和列数。 接下来 $n$ 行，每行包含 $m$ 个整数，表示迷宫中对应行的各个格子。 ## 输出格式 将答案输出到文件 `maze.out`。 输出一个整数，表示从 $(1,1)$ 到 $(n,m)$ 的最少移动次数。 ## 数据范围 - $1 \le n,m \le 100$。 - 数组中的元素仅为 $0$ 或 $1$。 - 起点 $(1,1)$ 和终点 $(n,m)$ 的值均为 $0$。 - 保证至少存在一条从起点到终点的通路。 ## 样例输入 ``` 5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 ``` ## 样例输出 ``` 8 ``` ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$128$ MB。