#O1038. 网格最短路

网格最短路

题目描述

给定 n×mn \times m 的网格,. 表示可以通行,# 表示障碍。从左上角 (1,1)(1,1) 出发,每次可以向上、下、左、右移动一格,求到右下角 (n,m)(n,m) 的最少步数;无法到达输出 -1。

题目类型

广度优先搜索

输入格式

第一行两个整数 n,mn, m。

接下来 nn 行,每行一个长度为 mm 的由 . 和 # 组成的字符串。

输出格式

一行一个整数,表示最少步数,无法到达输出 -1。

样例 #1

样例输入 #1

3 3
.#.
...
.#.

样例输出 #1

4

数据规模与约定

数据范围 说明
1≤n,m≤10001 \le n, m \le 1000 网格规模