题目描述

有一张 $n$ 行 $m$ 列的网格迷宫，. 表示可以走的空地，# 表示障碍。你从左上角 $(1,1)$ 出发，每一步可以走到上下左右相邻的空地，求走到右下角 $(n,m)$ 的最少步数；如果走不到，输出 $-1$。

输入格式

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

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

输出格式

一个整数，表示最少步数；不可达输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

5

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n,m\le 1000$，保证 $(1,1)$ 与 $(n,m)$ 都是空地。