题目描述

有一个 $n$ 行 $m$ 列的网格。. 表示可以走的空地，# 表示墙。

你从左上角 $(1,1)$ 出发，每次可以向上、下、左、右移动一格，不能走出网格、不能穿墙。

求到达右下角 $(n,m)$ 的最少步数；如果无法到达，输出 $-1$。

输入格式

第一行两个整数 $n, m$（$1 \le n, m \le 1000$）。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只含 . 和 #。

输出格式

一个整数，表示最少步数；无法到达输出 $-1$。

样例 #1

3 4
....
.##.
....

5

$(1,1) \to (1,2) \to (1,3) \to (1,4) \to (2,4) \to (3,4)$，共 5 步。

提示

对于 30% 的数据，$n, m \le 10$；对于 100% 的数据，$n, m \le 1000$。